【题解】CF1852C Ina of the Mountain

我们先从题目的一部分入手。

如果说，我们没有当一个数为 \(0\) 时，让这个数变成 \(k\) 的性质，我们如何求答案呢？

很简单，在图上就是：

绿色线段的长度加起来即为答案（本图中是 \(6\)）

我们考虑很显然地，将一个数从 \(0\) 变为 \(k\) 即为将一个数一开始加上 \(k\)

我们如果要让第 \(i\) 列格子前面的数的代价减小，那么一定会在 \(i\) 前面找一个 \(j\) 让 \([j,i-1]\) 的区间内的所有数都加上 \(k\)，而代价为 \(a_j+k - a_{j-1}\) 我们只需要将所有的 \(a_j+k-a_{j-1}\) 放进优先队列里面，每次取最小的，和现在的\(a_i-a_{i-1}\) 取 \(\min\) 即可。

code：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 2e5 + 8;
int n,k;
ll a[NN];
void solve(){
	scanf("%d%d",&n,&k);
	for(int i = 1; i <= n; ++i) scanf("%lld",&a[i]),a[i] %= k;
	a[n+1] = 0;
	priority_queue<ll, vector<ll>, greater<ll> > q;
	while(!q.empty()) q.pop();
	ll ans = 0;
	for(int i = 1; i <= n + 1; ++i){
		if(a[i - 1] == a[i]) continue;
		if(a[i - 1] > a[i]) q.push(a[i] + k - a[i - 1]);
		else{
			q.push(a[i] - a[i - 1]);
			ans += q.top();
			q.pop();
		}
	}
	printf("%lld\n",ans);
}
int T;
int main(){
	scanf("%d",&T);
	while(T--) solve();
}