题意：给你一个长度为n的序列。问你最少进行多少次操作，使得最终整个序列的值都为k
操作：选一段区间，然后把这段区间的数全减一。
这个序列还有一个特性，就是当一个数为0时，这个数会变成k。
解法：一眼丁真P1969 [NOIP2013 提高组] 积木大赛 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)，但这个没那么简单。
首先也是从上面这道橙题考虑，这道橙题的做法就是贪心，然后对于每一个相邻的两项且后项大于前项的，ans加上其差值就好了。
这个样子贪心是对的，因为我们选择一个区间，当我们去减这个区间最大的数的时候，小的数也跟着就剪完了。
然后我们想想这道题与上题的不同之处，那就是当我们还可以去把一个数减到0后再继续减，那样他就又变成一个大数了。所以当后项大于前项我们依然取差值，但反之我们就让后项加k再减前项。这是没有问题的。
所以当我们遇到前项大于后项时，可以考虑把黑色变成红色，然后就可以省掉下一次的后项大于前项的差了。然后你会神奇的发现，这种操作是具有传递性的。所以不管多远也可以用，而且用这个所抵消的后项减前项的差，就同理也可以传递了。于是我们开一个堆来维护这些操作得出的最小值，每次遇上要加后项减前项的差的时候，就从堆里拿最小的就好了。
#include<bits/stdc++.h> #define de cout<<111<<"\n"; #define fi first #define se second #define ll long long #define kx(a,b) ((a*b)%mod) #define kplus(a,b) ((a+b)%mod) #define lowbit(x) x&(-x); #define up(a,b) ((a-1ll)/b+1ll) typedef __int128 Int; using namespace std; const int N=1000010; const ll mod=998244353; //const int mod=1000000007; typedef pair<int,int> pii; ll fect[N], infect[N]; ll binpow(ll a,ll b,ll c){ ll ans=1; while(b){ if(b&1) ans=(Int)ans*a%c; a=(Int)a*a%c; b>>=1; } return ans;} int C(int a,int b){ return fect[a]*infect[b]%mod*infect[a-b]%mod;} void initzuhe(int n){ fect[0]=1;infect[0]=1; for(int i=1;i<=n;i++){ fect[i]=(fect[i-1]*i)%mod; } infect[n-1]=binpow(fect[n-1],mod-2ll,mod); for(int i=n-2;i>=1;i--) infect[i]=infect[i+1]*(i+1ll)%mod;} ll test[12]={2,3,5,7,11,13,17,19,23,29,31,37},maxn; bool check(ll a,ll n){ ll d=n-1,get=binpow(a,d,n); if(get!=1) return 1; while((d&1)^1) if(d>>=1,(get=binpow(a,d,n))==n-1) return 0; else if(get!=1) return 1; return 0;} bool miller_rabbin(ll n) { if(n<40){ for(int i=0;i<12;i++) if(test[i]==n) return 1; return 0; } for(int i=0;i<12;i++) if(check(test[i],n)) return 0; return 1;} ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b);} inline ll f(ll x,ll c,ll n){ return ((Int)x*x+c)%n;} ll pollard_rho(ll x){ ll s=0,t=0,c=1ll*rand()%(x-1)+1,val=1; for(int i=1;;i<<=1,s=t,val=1){ for(int j=1;j<=i;j++){ t=f(t,c,x); val=(Int)val*abs(t-s)%x; if(!(j%127)){ ll d=gcd(val,x); if(d>1) return d; } } ll d=gcd(val,x); if(d>1) return d; }} ll x,y; ll exgcd(ll a,ll b,ll &x,ll &y){ if(b==0){ x=1ll,y=0ll; return a; } ll temp=exgcd(b,a%b,x,y); ll z=x;x=y; y=z-a/b*y; return temp; } void solve(){ int n,k;cin>>n>>k;priority_queue<int,vector<int>,greater<int>>a; int pre=0; ll ans=0ll; for(int i=1;i<=n;i++){ int c;cin>>c;c%=k; if(c>=pre){ a.push(c-pre); ans+=a.top(); a.pop(); } else{ a.push(k+c-pre); } pre=c; } cout<<ans<<"\n"; } signed main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); srand((unsigned)time(NULL)); int t;cin>>t;while(t--) solve(); }