被这个题折磨了好久，决定写一篇题解
先考虑没有这个\(k\)的限制的情况，等价于对原来的\(a_i\)序列的差分数组\(b_i\),每次找到两个位置\(1\le x < y \le n\)，每次操作是使得\(b_x-1,b_y+1\),最终使得差分序列\(b\)变成0，那么所花费的代价为\(\sum_{i=1}^{n}\max (0,b[i])\),这是因为\(a_i\ge0\),所以\(b_i\)的前缀和都是大于等于0的，可以单独对\(b_i>0\)的位置进行\(-1\)的操作，后面对应的\(+1\)可以放在\(b_i<0\)的位置或者在\(b_{n+1}\)上。
然后考虑\(k\)的限制，当\(a_i\)减少到0时就变为\(k\)，其实就是让原数组的每个值，加上若干个\(k\)，那么序列就会转化成\(a_i+nk\)的形式，记作\(c_i\)然后这样我们就可以套用之前的公式，把\(c[i]\)的差分数组记作\(d[i]\)，答案就等于\(\sum_{i=1}^{n}d[i])\), 那么对于最优的阶，一定满足\(d[i]\le k\)的条件
证明：假设不满足，可以让\(c[i]\)减去\(k\),考虑对相邻的\(c[i]\)和\(c[i+1]\)的影响，如果原本\(c[i+1]>c[i]\),那么\(c[i]\)减去\(k\)对答案的贡献就是\(0\),因为\(d[i]\)减小了\(k\),\(d[i+1]\)增大了\(k\)。
否则，如果\(c[i]-k\ge c[i+1]\),答案会减少\(k\), 如果\((c[i+1]\le c[i]) \and (c[i+1]\ge c[i]-k)\),那么\(c[i]\)减去\(k\)会使得答案减少\(k-(k+c[i+1]-c[i])=c[i]-c[i+1] \ge 0\),所以，让\(c[i]\)减去\(k\)一定不会使得答案更差，所以可以一直这么减下去
那么可以考虑相邻的\(c[i]\)和\(c[i+1]\)，先假设他们都加上了相同的\(k\)，那么就是比较\(a_i\)的大小，分以下几种情况
- 如果\(a[i+1]\le a[i]\),根据上述计算答案的公式，那么它对答案的贡献就是0
- 如果\(a[i]<a[i+1]\)
如果什么都不动，它的贡献就是\(a[i+1]-a[i]\)
否则就考虑让\(a[i]\)和\(a[i+1]\)所加上的\(k\)的个数不同，因为要满足\(d[i]\le k\)的条件，让\(a[i]\)多加上一个\(k\),这样\(c[i]\ge c[i+1]\)，在\(i\)这个位置产生的贡献就是\(0\),但加上这个\(k\)不是白加的，需要找到一个\(1\le j\le i\),使得\([j,i]\)的位置都加上一个\(k\)。注意到，如果\(a[j]> a[j-1]\)，这样产生的贡献为\(k\)，这样不如\(a[i+1]-a[i]\),所以选取的方案一定满足\(a[j] \le a[j-1]\),这样的贡献为\(k+a[j]-a[j-1]\)
考虑用一个小根堆维护所有满足\(a[i-1]\le a[i]\)的位置，当我们第一次枚举到\(a[i-1] \le a[i]\)的位置时，答案加上0，但是这步操作时可以反悔的，所有要把\(a[i]+k\)的情况存入堆中，即\(k+a[i]-a[i-1]\)，当碰到\(a[i-1]<a[i]\)时拿堆中最小的元素，和\(a[i]-a[i-1]\)取\(min\)。如果需要弹出堆的元素，那么还需要把\(a[i]-a[i-1]\)放到堆里，因为这个时候\(c[i]<c[i-1]\)，我们默认它对答案没有贡献，但这一部也是可以反悔的，可以让\(c[i]\)再加上k，在后面可能会用到。
代码很简单
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N=2e5+10,INF=2e9,mod=1e9+7;
void solve(){
int n,k;
cin>>n>>k;
priority_queue<int,vector<int>,greater<int>>heap;
int last=0;
ll res=0;
for(int i=1;i<=n;i++){
int x;
cin>>x;
x%=k;
if(x<=last) heap.push(k+x-last);
else {
if(!heap.empty()&&x-last>heap.top()){
res+=heap.top(),heap.pop();
heap.push(x-last);
}
else res+=x-last;
}
last=x;
}
cout<<res<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
}