[AGC023D] Go Home

wzxx · 2021-03-24 14:50:15 · 题解

题目链接

题目中，每一个人的投票策略都是投 “使自己尽快到家” 的方向。

第一眼看上去，以为等价于 “投自己家的方向” ，其实并不然。

观察样例，发现第一个样例就很好地解释了他们的投票策略。

输入：

输出：

显然，车行驶的路线是 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) 的算法。

代码有点小细节。

#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;
}