P9519 pay 题解

· · 题解

题目传送门

本篇题解使用了跟其它题解思路差别较大奇特的解法。

思路

二分

首先，注意到每一个员工的快乐值都关于 k 单调不减，考虑通过二分 k 的值来解决问题。

判定

现在我们需要解决以下问题：已知 k 的值，判断是否能使所有员工的快乐值都能达到期望。

依照题意，对于任意一名发工资的员工，其对周围的员工快乐值的影响可以抽象为左右两个有边界的一次函数，如下图。

该员工所在的点视为 (b_i,k)，两个一次函数的斜率分别为 1,-1，因此，我们可以把这两个一次函数的表达式写出来：

y=x+k-b_i y=-x+k+b_i

现在有多个这种一次函数，只要把它们叠加在一起（作一次多项式加法）就能求出来每一个员工最终的快乐值。

有界，叠加……这不就是差分嘛！只不过我们要用差分维护一次函数的系数！

这里有一个小细节需要注意：中间横坐标为 b_i 的点只能处理一次，千万不要在左面的一次函数差分一次之后，在右面又差分一次（具体见代码中的 b[i]+1）。

最后，对从左到右扫描每一个员工，带入横坐标（即编号）计算出其快乐值，就能判断出当前 k 值是否能满足要求啦！

AC代码

#include<bits/stdc++.h>
#define rint register int
#define cint const int
#define ll long long
using namespace std;
cint N=1e6+5;
int n,m,a[N],b[N];
void input(){
    cin>>n>>m;
    for(rint i=1;i<=n;++i){
        cin>>a[i];
    }
    for(rint i=1;i<=m;++i){
        cin>>b[i];
    }
    return;
}
void work(){    
    ll x[n+5],y[n+5];
    int l=1,r=1e9+n+5,k,tl,tr,ju;
    ll tx,ty,tmp;
    while(l<r){
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        ju=0;
        k=(r+l)>>1;
        for(rint i=1;i<=m;++i){
            tl=b[i]-k;
            if(tl<1) tl=1;
            ++x[tl];
            y[tl]+=k-b[i];
            --x[b[i]+1];
            y[b[i]+1]-=k-b[i];
            tr=b[i]+k;
            if(tr>n) tr=n;
            --x[b[i]+1];
            y[b[i]+1]+=k+b[i];
            ++x[tr+1];
            y[tr+1]-=k+b[i];
        }
        tx=ty=0;
        for(rint i=1;i<=n;++i){
            tx+=x[i];
            ty+=y[i];
            tmp=tx*i+ty;
            if(tmp<a[i]){
                ju=1;
                break;
            }
        }
        if(ju) l=k+1;
        else r=k;
    }
    cout<<l;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    input();
    work();
    return 0;
}