Tokitsukaze and Musynx

原题链接

TAG：枚举

思路

对于每个判定分，我们可以将其全部偏移到 \(-\infty\) 的位置上，然后从小到大（排序）枚举到下一个区间所需要的偏移分数，在此过程中取最大值即可。

时间复杂度 \(O(n\log{n})\)

代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

void solve() {
    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i];
    }

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    d++;

    array<int, 5> v;
    for (int i = 0; i < 5; i++) {
        cin >> v[i];
    }

    LL res = 0;
    vector<pair<int, int>> events;
    for (int i = 0; i < n; i++) {
        res += v[0]; // 全部偏移到负无穷
        // 根据偏移变化，计算总分数的变化
        events.push_back({a - x[i], v[1] - v[0]});
        events.push_back({b - x[i], v[2] - v[1]});
        events.push_back({c - x[i], v[3] - v[2]});
        events.push_back({d - x[i], v[4] - v[3]});
    }

    sort(events.begin(), events.end());

    LL ans = res;
    for (auto [_, x] : events) {
        res += x;
        ans = max(ans, res);
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}