题解：P11511 [ROIR 2017 Day 2] 大型直线对撞机

xuyifei1599 · 2025-01-07 14:09:54 · 题解

这道题，我们只需处理出所有可能对撞的粒子湮灭的时间，由于肯定是相互最近的反方向粒子对撞，所以我们就可以用栈去维护目前最近的反方向的粒子。最后给这些时间排一个序，在查找时间的时候二分查找即可。

下面附上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node {
    int x, v;
} a[200005];
int n, m, t[200005], ans, sum[200005], num[200005], cnt;
stack<int> st;
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i].x >> a[i].v;
        if (a[i].v == -1) {
            if (st.empty()) {
                ans ++;
            } else {
                int tmp = st.top();
                st.pop();
                num[++cnt] = (a[i].x - a[tmp].x) / 2;
                if ((a[i].x - a[tmp].x) % 2 == 1) {
                    num[cnt] ++;
                }
                sum[cnt] = num[cnt];
            }
        } else {
            st.push(i);
        }
    }
    while (!st.empty()) {
        ans ++;
        st.pop();
    }
    sort(sum + 1, sum + 1 + cnt);
    cin >> m;
    for (int i = 1; i <= m; i ++) {
        cin >> t[i];
        if (t[i] >= sum[cnt]) {
            cout << ans << "\n";
            continue;
        }
        int j = upper_bound(sum + 1, sum + 1 + cnt, t[i]) - sum;
        cout << ans + (cnt - j + 1) * 2 << "\n";
    }
    return 0;
}