自动搬运

查看原文

来自洛谷，原作者为

	引领天下 用6年时间，讲好一个笑话。

搬运于2025-08-24 22:49:08，当前版本为作者最后更新于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;
}