luogu 3407 散步

题目链接

题意

按从左到右的顺序给出数轴上的一群人，有人向左走，有人向右走，一旦两人相遇就会停在当前位置，后来走到该位置的人也会停在该位置。问经过一段时间这些人分别在什么位置。

思路

可以将这些人分为若干组，同一组中的人全部相向而行，呈>>><<<的态势。这一组人最终的位置就取决于中间两个人的位置，只要知道他们有没有相遇，如果相遇在哪个点，其他所有人的位置都决定了。

再注意特判一下最左边一直向左走的人和最右边一直向右走的人即可。

时间复杂度(O(n)).

Code

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
LL p[maxn], t;
LL d[maxn];
LL max(LL a, LL b) { return a > b ? a : b; }
LL min(LL a, LL b) { return a < b ? a : b; }
LL n, q;
int main() {
    scanf("%lld%lld%lld", &n, &t, &q);
    for (LL i = 1; i <= n; ++i) scanf("%lld%lld", &p[i], &d[i]);
    LL i = 1, j = n;
    for (; i <= n; ++i) {
        if (d[i] == 1) break;
        p[i] -= t;
    }
    for (; j > 0; --j) {
        if (d[j] == 2) break;
        p[j] += t;
    }

    LL s = i, pos;
    LL mid;
    d[j+1] = 1;
    for (; i <= j; ++i) {
        if (d[i] == 1 && d[i+1] == 2) mid = p[i]+p[i+1] >> 1, pos = i+1;
        else if (d[i] == 2 && d[i+1] == 1) {
            for (LL k = s; k < pos; ++k) p[k] = min(p[k]+t, mid);
            for (LL k = pos; k <= i; ++k) p[k] = max(p[k]-t, mid);
            s = i+1;
        }
    }

    while (q--) {
        LL x;
        scanf("%lld", &x);
        printf("%lld
", p[x]);
    }
    return 0;
}