P9519-pay-题解

发表于 2023-08-14 分类于信奥，题解阅读次数：

原题链接：Link

思路分析

首先二分比较显然，如果某一个工资能满足，更高的工资一定也能满足，可以二分。

判断函数有两种方法：

维护差分

维护差分数组的差分来实现区间加等差数列，在全部加完之后做两次前缀和。

参考代码：

code

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

const int maxn = 1e6 + 5;

int n, m;
long long a[maxn], d[maxn];
int b[maxn];

bool check(long long x) {
    memset(d, 0, sizeof d);
    for (int i = 1; i <= m; i++) {
        if (b[i] < x) {
            d[1] += x - b[i] + 1;
            d[2] -= x - b[i];
            d[b[i] + 1]--;
        }
        else {
            d[b[i] - x + 1]++;
            d[b[i] + 1]--;
        }

        d[b[i] + 1]--;
        if (b[i] + x <= n) d[b[i] + x + 1]++;
    }
    for (int i = 1; i <= n; i++) d[i] += d[i - 1];
    for (int i = 1; i <= n; i++) d[i] += d[i - 1];
    for (int i = 1; i <= n; i++) {
        if (d[i] < a[i]) return false;
    }
    return true;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", a + i);
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", b + i);
    }
    long long l = 0, r = 2000000000, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}

统计贡献

一个员工分别可以向左向右延伸 \(x\) 个人，在这左右两个区间内的工资会对员工产生贡献。

从左到右扫一遍员工，每移动一格，左右区间就跟着移动一格。这个时候，左区间里的贡献全部减一，右区间的贡献全部加一，可以用两个变量来维护左右区间的工资数目。

预处理出第一个员工的贡献，然后从头扫到尾即可。

参考代码：

code

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

const int maxn = 1e6 + 5;

int n, m;
long long a[maxn], d[maxn];
bool book[maxn];

bool check(long long x) {
    long long sum = 0, cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++) {
        if (book[i]) sum += max(0LL, x - (i - 1));
        if (book[i] && i <= x) cnt2++;
    }
    if (sum < a[1]) return false;
    for (int i = 2; i <= n; i++) {
        if (i + x - 1 <= n && book[i + x - 1]) cnt2++;
        if (book[i - 1]) cnt2--, cnt1++;
        sum += cnt2;
        sum -= cnt1;
        // if (x == 5) printf("%lld\n", sum);
        if (sum < a[i]) return false;
        if (i - x >= 1 && book[i - x]) cnt1--;
    }
    return true;
}

int main() {
    scanf("%d %d", &n, &m);
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", a + i);
        if (a[i] != 0) flag = false;
    }
    if (flag) {
        printf("0\n");
        return 0;
    }
    for (int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        book[x] = true;
    }
    long long l = 1, r = 2000000000, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}