Codeforces #887 : Div1 C. Ina of the Mountain

これまたコードが短め。
https://codeforces.com/contest/1852/problem/C

問題

整数列Aと整数Kが与えられる。
Aの区間を指定すると、区間内の値が1減る。ただしA[i]=0となった場合、A[i]=Kになる。
Aの全要素をKにするには、最小何回操作が必要か。

解法

mod Kで考えると、結局Aの全要素を0にする問題となる。
A[0]=A[N+1]=0を加えたうえで、mod Kで取ったAの階差数列を考える。
その和はKの倍数となる。

基本的にA[i]とA[i+1]の差D[i]に対し、処理がD[i]回必要だが、sum(D)/K回だけはそれを行わなくて良い。
よってAがwrap around1回行うたびに1回コストD[i]を払わずに済むので、コストの低い順にコストを払うようにしよう。

int T,N,K;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		int pre=0;
		ll ret=0;
		multiset<int> D;
		FOR(i,N) {
			cin>>x;
			x%=K;
			if(x>pre) {
				D.insert(x-pre);
				ret+=*D.begin();
				D.erase(D.begin());
			}
			else {
				D.insert(K+x-pre);
			}
			pre=x;
		}
		
		cout<<ret<<endl;
		
	}
}

まとめ

このテクなんか過去にもSRMやAtCoderで見た気がする…。