Atcoder Grand Contest 023D

Atcoder Grand Contest 023D - Go Home

题目大意

• 一条路上有$N$幢房子，每幢房子住有$X_i$个人，最初汽车从某个地点$S$出发，装着所有的人，汽车每次走一个单位，向左或向右由所有人投票决定，少数服从多数，如果汽车到达了自己所住的房子则下车。
• 每个人都会尽可能使自己尽早到达，求最晚到达的人的到达时间。
• $N\le 10^5$

题解

• 第一眼以为维护前缀和后缀和，每次最最贪心地判断左右哪边人多久往哪边走，但一看样例就会发现这样是错的，
• 也就是说，对于每个人而言，不一定每次都向着自己想去的地方投票就一定能更早到达。
• 举个例子，加入当前左边依次有两幢房子，人数为$A,B$，右边一幢房子人数为$C$，
• 满足$A<C$，$B<C$，$A+B>C$，
• 考虑$A$中的人会如何投票？
• 如果$A$向左投，$B$也向左投，$C$会向右投，那么汽车会向左移动，可是并不能一直移动到$A$
• 直到$B$的人下车后，向左的人数就小于向右的人数了，那么汽车右会一直移动到最右边再回来到$A$，
• 因此$A$中的人会先投右边， 让$C$先到，他们自己便也可以更早到达。
• 这是为什么呢？考虑更一般的情况：
• 若当前最左边的人数为$A$，最右边的人数为$B$，满足$A<B$，中间大小不考虑（$A>B$同理），
• 如果汽车一直向左走，虽然会不断靠近$A$，但总会有一个时刻，向左的人数小于向右的人数了，而使汽车向右走去，绕到最右端才回来，
• 这样看的话，若$A<B$，则$A$一定会比$B$更晚到，且$B$到达之后，再到达$A$之间所用的时间是确定的，即为二者之间的距离，那么$A$为了自己先到，会尽可能让$B$先到，所以$A$会向右投票，
• 于是，可以忽略$A$的存在，直接给$B$加上$A$，然后总时间加上二者之间的距离，于是剩下的部分转为原问题的一个子问题，按同样的思路继续求解，只需要记录当前子问题的区间$[l,r]$，可以用递归实现，复杂度$O(n)$。
• 在这个过程中，相当于推出汽车运动的反向过程，给$B$加上$A$相当于汽车有一个$B$到$A$的移动过程。
• 那边界条件是什么？
• 根据题意，如果子问题的整个区间在$S$的左侧或右侧了，那么所有人的意见就会统一进行，按顺序直接走完。
• 要注意，如果当前子问题中汽车的移动反向和上一次相同的话，那么不用计入答案，因为这一次的答案会被上一次包含。

代码

#include<cstdio> 
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 100010
ll ans = 0;
int t;
struct {
	int x; ll s;
}a[N];
void ct(int l, int r, int o) {
	if(a[l].x >= t) {
		ans += a[r].x - t;
		return;
	}
	if(a[r].x <= t) {
		ans += t - a[l].x;
		return;
	}
	if(a[l].s >= a[r].s) {
		a[l].s += a[r].s;
		if(o != 0) ans += a[r].x - a[l].x;
		ct(l, r - 1, 0);
	}
	else {
		a[r].s += a[l].s;
		if(o != 1) ans += a[r].x - a[l].x;
		ct(l + 1, r, 1);
	}
}
int main() {
	int n, i;
	scanf("%d%d", &n, &t);
	for(i = 1; i <= n; i++) scanf("%d%lld", &a[i].x, &a[i].s);
	ct(1, n, -1);
	printf("%lld", ans);
	return 0;
}