自动搬运

查看原文

来自洛谷，原作者为

	Ch1F4N HN 初三最菜 OIer|| 新的赛季 rp ++

搬运于2025-08-24 23:06:13，当前版本为作者最后更新于2025-02-03 21:32:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下文认为是把 $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;
}