问题 E: JackRabbit Slim

时间限制: 1 Sec  内存限制: 128 MB
提交: 23  解决: 1

题目描述

We all love rabbits, right? Unfortunately, they don’t even like us, rather, they love carrots instead!
They love carrots so much that they would do anything to get to a carrot, even running. That might sound easy, but rabbits are lazy, it’s the jackrabbits who are the active ones. That’s why this problem is about jackrabbits and not rabbits. In fact,it’s about a very specific black-tailed jackrabbit, named Slim.
Earlier this morning, before the contest started, a truck loaded with carrots passed through the road by Slim’s house. Slim was so lucky that n carrots dropped off on the road. We number them 1 to n from left to right. When Slim left home, he found a carrot. After taking a look around, his plan for the day became clear: Locate the closest carrot, get to it and eat it, then repeat.
The road by Slim’s house is a straight road of length 109 and the i-th carrot on the road is at coordinate xi .
Consider Slim starts his day by standing at the position of the j-th carrot and eating it. Then as long as there are more carrots, he follows the following steps:
• Locate the closest remaining carrot. If there are two closest carrots, choose the one to the right.
• Run to it and eat it. Simple!
For each value of j, we call Dj the total distance Slim runs if it starts the day by eating carrot j. For an unknown reason,we are interested in finding the sum of all Dj values, for all values of j (1 ⩽ j ⩽ n).

 

输入

The first line of the input contains a single integer n (1 ⩽ n ⩽ 105 ), the number of carrots. The second line of the input contains n space-separated distinct integers x1,...,xn (0 ⩽ xi ⩽ 109 ). The coordinates of the carrots are in an increasing order.

 

输出

Output an integer value, which is the sum of all Dj values (for j from 1 through n).

 

样例输入

复制样例数据

6
1 14 19 20 21 24

样例输出

168

这题花了2天时间终于写出来了，不容易，其实也不是很难。

假设一只兔子在往左吃萝卜，如果需要折返去吃右边的萝卜，说明左边下一个萝卜到起点的距离至少是当前位置到起点距离的两倍，因此折返次数是 logn 的。

知道了这个后，分类讨论下:

1.往左走：满足x[l] - x[l - 1] < x[r] - x[l] 即 2x[l] - x[l - 1] < x[r];(l表示当前到的左端点，r表示右端点,l + 1 ~ r - 1已经全部吃完)

2.往右走：满足x[r] - x[r - 1] <= x[r - 1] - x[l] 即 x[r] - 2x[r - 1] <= -x[l];

用ST表分别维护下，然后二分下，总得复杂度为O(nlognlogn(差不多，可能还会小))

 

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n, dp0[25][100005], dp1[25][100005];
LL a[100005], bin[25], Log[100005];

int fun0(int l, int r, int num, int now){
	int ans = r;
	while(l <= r){
		int mid = (l + r) >> 1;
		int t = Log[now - mid];
		LL maxx = max(dp0[t][mid + 1], dp0[t][now - bin[t] + 1]);
        if(maxx < num) ans = mid, r = mid - 1;
        else l = mid + 1;
	}
	//printf("%d\n", ans);
	return ans;
}

int fun1(int l, int r, int num, int now){
	int ans = l;
	while(l <= r){
		int mid = (l + r) >> 1;
		int t = Log[mid - now];
		LL maxx = max(dp1[t][now + 1], dp1[t][mid - bin[t] + 1]);
        if(maxx <= -num) ans = mid, l = mid + 1;
        else r = mid - 1;
	}
	//printf("%d\n", ans);
	return ans;
}

int main()
{
	//freopen("18.in", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%lld", &a[i]);
	}
	a[0] = a[1], a[n + 1] = a[n];
	bin[0] = 1, Log[0] = -1;
	for (int i = 1; i <= 20; i++) bin[i] = bin[i - 1] << 1;
	for (int i = 1; i <= n; i++) Log[i] = Log[i / 2] + 1, dp0[0][i] = 2 * a[i] - a[i - 1], dp1[0][i] = a[i] - 2 * a[i - 1];
	for (int i = 1; i <= Log[n]; i++){
		for (int j = 1; j + bin[i] - 1 <= n; j++){
			dp0[i][j] = max(dp0[i - 1][j], dp0[i - 1][j + bin[i - 1]]);
			dp1[i][j] = max(dp1[i - 1][j], dp1[i - 1][j + bin[i - 1]]);
		}
	}
	LL ans = 0;
	for (int i = 1; i <= n; i++){
		int now = i, l = i - 1, r = i + 1;
		if(now == 1 || now == n) ans += a[n] - a[1];
		else{
			int f = 0;
			if(a[i] - a[l] >= a[r] - a[i]) f = 1;
			while(1){
				int p;
				if(!f) p = fun0(1, now - 1, a[r], now), ans += a[now] - a[p], now = p, l = now - 1, f = 1;
				else p = fun1(now + 1, n, a[l], now), ans += a[p] - a[now], now = p, r = now + 1, f = 0;
				if(r > n || l < 1) break;
			}
			if(l >= 1) ans += a[now] - a[1];
			else if(r <= n) ans += a[n] - a[now];
		}
		//printf("num = %d %d %d %lld\n", i, l, r, ans);
	}
	printf("%lld\n", ans);

	return 0;
}
/**/

/*
30
0 2 3 4 23 176 410 412 524 543 550 553 555 586 7587 7588 7886 7887 7890 7891 9699 9701 9708 9714 9733 9909 9949 9951 9973 10000
*/

/*323281*/