[AGC023D] Go Home
wzxx
2021-03-24 14:50:15
[题目链接](https://www.luogu.com.cn/problem/AT3955)
题目中，每一个人的投票策略都是投 “使自己尽快到家” 的方向。
第一眼看上去，以为等价于 “投自己家的方向” ，其实并不然。
观察样例，发现第一个样例就很好地解释了他们的投票策略。
输入：
```cpp
3 2
1 3
3 4
4 2
```
输出：
```cpp
4
```
显然，车行驶的路线是 2 → 1 → 2 → 3 → 4 ，先左再右。
但是一开始时，住在右边的人明明比住在左边的人多 3 个，为什么不往右开呢？
假设先往右开，在位置 3 有 4 个人下了车，此时支持往右开的只剩 2 个人，被住在左边的 3 个人碾压，势单力薄的他们根本无法使车继续往右开，只能让车先开到 1 再开回 4 ，这还不如一开始就往左开。
所以，在开始的时候，住在 4 的 2 个人投了左方向，使得车先往左开。
可以发现，人们之所以不一定会投自己家的方向，是因为在驶向自己家的途中，有一批人会下车，使得车到不了自己家又开回去了，得不偿失，所以这一部分人会选择投反方向。
我们考虑最左端的房子 $X_l$ 和最右端的房子 $X_r$ 。
如果 $S < X_l$ 或 $S > X_r$ ，可以直接计算。
考虑 $X_l < S < X_r$ 。不难发现，如果 $P_l \geq P_r$，车子一定会先到达 $X_l$ 再到达 $X_r$ 。
假设车子先往 $X_r$ 的方向走， 因为 $P_l \geq P_r$ ，所以还没等走到 $X_r$ ，右边的票数就会减少到小于左边的票数，车子就会调头， 住在 $X_r$ 的人就会反水投左边。所以不管怎么样， $X_r$ 的人都会投左边，所以车子必然先到 $X_l$ 再到 $X_r$ 。
既然这样，我们干脆让 $X_r$ 的人都搬到 $X_l$ ，累积上 $X_r - X_l$ 的代价后递归处理。当 $P_l < P_r$ 时同理。边界条件为 $S < X_l$ 或 $S > X_r$ 。
于是，我们就得到了一个时间复杂度 $O(n)$ 的算法。
代码有点小细节。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100005;
int n = 0, S = 0, x[N];
long long p[N];
long long rd() {
long long x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
long long Sol(int l, int r, int opt) {
if (S < x[l]) return x[r] - S;
if (S > x[r]) return S - x[l];
if (p[l] >= p[r]) {
p[l] += p[r];
return Sol(l, r - 1, 1) + (opt ? 0 : (x[r] - x[l]));
}
p[r] += p[l];
return Sol(l + 1, r, 0) + (opt ? (x[r] - x[l]) : 0);
}
int main() {
n = rd(), S = rd();
for (int i = 1; i <= n; i++)
x[i] = rd(), p[i] = rd();
printf("%lld", Sol(1, n, (p[1] >= p[n]) ? 0 : 1));
return 0;
}
```