P9519题解

引领天下 · 2023-08-12 18:27:05 · 题解

看到这道题第一反应就是二分，二分最终到底发多少工资。

那么现在问题就变成了，如何在线性时间内判断一个给定的 k 是否能满足题意？

我们意识到，朴素的 n^2 的统计方法中有大量无用的计算——当第 i 个人发工资的时候，他会同时对 i+1\sim i+k 和 i-k\sim i-1 产生贡献，并且这个贡献恰好依次递减。

这启发我们思考，能否通过重复减一的方式来获得某个位置对当前位置的贡献呢？

答案当然是肯定的。

我们定义一个队列 q 用于存放所有对当前位置有贡献的位置，设 s 表示队列中所有元素的贡献之和，那么每次后移的时候只需要 s\rightarrow s-|q|（其中 |q| 表示 q 中的元素个数），就可以方便的更新当前位置能获得的贡献。如果一个位置不再对当前位置产生贡献，那么将他踢出队列即可。

这样我们就获得了 i 之前的发工资的人对 i 产生的贡献。

然后再逆序做一遍，就可以获得 i 之后的发工资的人对 i 产生的贡献。这两部分加起来，再考虑 i 自身发的工资，就得到 i 最终的满意度，和 a_i 比较即可。

这样我们就在线性复杂度内完成了对某个 k 是否符合题意的检查，算法总复杂度 O(n\log n)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],ans,m,b,l=1,r,mid;
bool s[1000005];
long long c[1000005];
inline bool check(int k){
    queue<int> q;
    long long sum=0;
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++){
        sum-=q.size();
        if(!q.empty()&&i-q.front()>=k)q.pop();
        if(s[i])sum+=k,q.push(i);
        c[i]+=sum;
    }
    while(!q.empty())q.pop();sum=0;
    for(int i=n;i;i--){
        sum-=q.size();
        if(!q.empty()&&q.front()-i>=k)q.pop();
        if(s[i])sum+=k,q.push(i);
        c[i]+=sum;
        if(s[i])c[i]-=k;//注意特判，如果 i 本身发了工资，那么会被统计两次，需要减去重复的。
    }
    for(int i=1;i<=n;i++)if(c[i]<a[i])return 0;
    return 1;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],r=max(r,a[i]);
    for(int i=1;i<=m;i++)cin>>b,s[b]=1;
    r+=n;//需求最高的人不一定发工资，所以加上 n 之后才是真正的二分上限。
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
}