题解：P11301 [NOISG 2021 Finals] Password

· · 题解

下文认为是把 a 序列通过操作变为 b 序列。

首先我们知道每个位置需要操作的次数形如 c_i + l \times (k+1)，其中 c_i = (b_i + k + 1 - a_i) \bmod (k+1)。

假设你知道了最后每个位置被操作的真实次数 d_i，根据积木大赛的结论，操作次数为 \sum \max(0,d_i - d_{i-1})，下文令 e_i = d_i - d_{i-1}。

你发现你给一个位置 i 的 d_i \gets d_i + (k+1)，相当于使得 e_{i+1} \gets e_{i+1} - (k+1),e_i \gets e_i + (k+1)，也就是把后面一个位置的 k+1 移到前面一个位置，通过反复操作，这两个位置可以不相邻。所以我们认为一开始 e_i=c_i-c_{i-1} 然后可以通过操作调整 e_i 的值。

然后来分析一下，首先一个位置要么将 k+1 移到前面要么被后面的数给了 k+1，因为两种操作同时存在可以转化为不同时存在。

然后给初始 e_i 为负的加，e_i 为正的减是可能优的，否则一定不优。且正负性反转后再操作也是不优的，所以一个点上能进行的操作是确定的。

到这里是一个二分图最大权匹配模型（e_i 为负的位置 i 有一些权值为 0 的左侧点和一个权值为负的左侧点，e_i 为正的位置 i 有一些权值为 k+1 的右侧点和一个权值为正的右侧点），由于限制是只能将后面的数移到前面，所以我们从后往前去贪心，注意到可能将不优的操作反悔，所以考虑反悔贪心。看上去会进行的形如权值为 0 的左侧点和权值为 k+1 的右侧点的匹配数量是很多的（其实并不存在这种匹配，因为 c 序列值域是 [0,k]，但是按照下面的方法特殊处理仍然是对的，在这里放出做法用于作为处理其他类似的问题的一个参考），而这类匹配一定最优，不会反悔，所以直接记录下右侧权值为 0 的点的数量，左侧权值为 k+1 的点的数量和这类匹配的数量，剩余的匹配和反悔用堆维护即可。时间复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5+114;
int n,a[maxn],b[maxn],k;
int ans;
priority_queue<int> P;
int cZ;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    k++;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        if(b[i]>=a[i]) a[i]=b[i]-a[i];
        else a[i]=b[i]+k-a[i];
    }
    for(int i=n;i>=1;i--) a[i]-=a[i-1],ans+=max(0*1ll,a[i]);
    for(int i=n;i>=1;i--){
        if(a[i]>0){
            cZ+=(a[i]/k);
            P.push(a[i]%k);
        }else if(a[i]<0){
            int cnt=(-a[i])/k;
            int f=(-a[i])%k-k;
            int p=min(cZ,cnt);
            ans-=p*k;
            cZ-=p,cnt-=p;
            while(cnt>0&&P.size()>0){
                ans-=P.top();
                P.pop();
                cnt--;
            }
            if(f==-k) continue;
            if(cZ>0){
                cZ--;
                ans-=(k+f);
                P.push(-f);
            }else{
                if(P.size()>0&&P.top()+f>0){
                    ans-=(P.top()+f);
                    P.pop();
                    P.push(-f);
                }
            }
        }   
    }
    cout<<ans<<'\n';
    return 0;
}