P9519 pay 题解。

1. 题解

一眼二分答案，然后考虑如何快速判断当前 \(k\) 满足题意。

首先把一个位置左右两边的贡献拆开，这样就不需要考虑绝对值了。

对于左边的贡献，我们从左到右扫一遍，维护一个队列和一个 \(\mathrm{sum}\)，\(\mathrm{sum}\) 表示当前位置 \(i\) 左边的贡献，队列表示这些贡献的位置。

每次 \(i\) 向后移动，\(\mathrm{sum}\) 减去队列长度，并且弹出队列中 \(k - d \le 0\) 的元素。

右边的贡献同理，算完贡献后和 \(a_i\) 比较即可。

时间复杂度 \(O(n \log V)\)，\(V\) 为值域。

2. Code

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e6 + 5;
int n, m, a[N], b[N];
long long l, r = 1e10, c[N], sum, cnt;
bool vis[N];
queue<int> Q;
bool check(long long k) {
    memset(c, 0, sizeof(c));
    sum = cnt = 0, Q = {};
    for (int i = 1; i <= n; i++) {
        sum -= cnt;
        if (cnt && k - (i - Q.front()) == 0) Q.pop(), --cnt;
        if (vis[i]) Q.push(i), ++cnt, sum += k;
        c[i] += sum;
    }
    sum = cnt = 0, Q = {};
    for (int i = n; i >= 1; i--) {
        sum -= cnt;
        if (cnt && k - (Q.front() - i) == 0) Q.pop(), --cnt;
        c[i] += sum;
        if (vis[i]) Q.push(i), ++cnt, sum += k;
    }
    for (int i = 1; i <= n; i++)
        if (c[i] < a[i]) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i], vis[b[i]] = true;
    while (l < r) {
        long long mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}