官方题解

题目大意

每次操作可以将任意个舞台灯光亮度 $+1$ 或 $-1$ ，求所有舞台灯光调整为目标值的最少操作次数。

解题思路

首先我们会发现，如果同时对第 $i$ 个舞台使用 $+1$ 操作和 $-1$ 操作，答案一定不会变得更优。因此我们可以将所有数分成两类，一类只使用 $+1$ 操作，一类只使用 $-1$ 操作。

所以我们可以对每一个舞台都分别计算出只用 $+1$ 操作和 $-1$ 操作，并用 pair<int,int> 存储，按照第一关键词排序，此时不难发现，如果第 $i$ 个舞台灯光只用 $+1$ 操作最优，那么 $[1,i]$ 的舞台灯光都用 $+1$ 操作最优，剩下的 $[i+1,n]$ 都用 $-1$ 操作。

因此可以预处理使用 $-1$ 操作的后缀 $max$ ，枚举分界点 $i$ ，计算第 $i$ 的花费和 $i+1$ 的后缀 $max$ 之和，统计最小值即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int INF = 1e9+10;

int n,m;
int a[N],b[N];
pair<int,int> p[N];
int suf[N];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];

    for(int i=1;i<=n;i++){
        if(b[i]>a[i]) p[i]={b[i]-a[i],m-(b[i]-a[i])};
        else p[i]={m-(a[i]-b[i]),a[i]-b[i]};
    }
    sort(p+1,p+n+1);

    suf[n+1]=0;
    for(int i=n;i>=1;i--){
        suf[i]=max(suf[i+1],p[i].second);
    }

    int res=INF;
    for(int i=0;i<=n;i++){
        res=min(res,p[i].first+suf[i+1]);
    }
    cout<<res<<endl;
}

int main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
    return 0;
}