题解：AT_abc395_f [ABC395F] Smooth Occlusion

· · 题解

题意

有两个长度为 n 的序列 u_i 和 d_i，每次操作可以把一个正数减一，问最少经过次操作使得：

  1. 存在 H 使所有 u_i+d_i=H。
  2. 序列中相邻两个数的差小于等于 x。

思路

这道题可以二分答案去做。

只需要确定 H，答案就是所有数字的总和减去 H\times n。

二分答案 H，下界是 0，上界是 \min(u_i+d_i)。

设 U_i,D_i 分别表示操作完后的 u_i 和 d_i。因为 U_i+D_i=H，所以只要一个确定了，另一个也确定，那我们就只考虑 U_i。

因为每次操作只能减少，所以有 U_i\le u_i,D_i\le d_i。

对于 D_i=H-U_i\le d_i 推出 U_i\ge H-d_i。

又因为每个数都要大于等于 0 且小于等于 H。所以 U_i 的范围是区间 [\max(0,H-d_i),\min(u_i,H)]。

对每个 U_i，记录它的取值区间左端点 L 和右端点 R。

第 i 个数的取值区间必须是两个约束的交集：

  1. 自身的区间 [\max(0,H-d_i),\min(u_i,H)]。
  2. 能够和前一个数的差不超过 x，即必须落在区间 [L_{i-1}-x,R_{i-1}+x] 内。

因此，对每个 i，L_i=\max(0,H-d_i,L_{i-1}-x),R_i=\min(H,u_i,R_{i-1}+x)。

如果对于某个 i，L_i>R_i，说明不合法。check 函数就是这样写的。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,x,u[N],d[N];
bool check(int H) {
    int L=max(0ll,H-d[1]),R=min(u[1],H);
    if(L>R) return 0;
    for(int i=2;i<=n;i++){
        int curL=max(0ll,H-d[i]),curR=min(u[i],H);
        curL=max(curL,L-x),curR=min(curR,R+x);
        if(curL>curR) return 0;
        L=curL,R=curR;
    }
    return 1;
}
signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>x;
    int sum=0;
    for(int i=1; i<=n; i++) cin>>u[i]>>d[i];
    for(int i=1; i<=n; i++) sum+=u[i]+d[i];
    int maxn=1145141919810ll;
    for(int i=1; i<=n; i++) maxn=min(maxn,u[i]+d[i]);
    int l=0,r=maxn,anss=0;
    while(l<=r) {
        int mid=(l+r)/2;
        if(check(mid)) anss=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<sum-n*anss;
    return 0;
}