Codeforces Round 887 (Div. 1) C. Ina of the Mountain(思维题/反悔贪心 值模k意义下区间减1使所有值为0的最小操作次数)_codeforces ina of the mountain

题目

t(t<=1e5)组样例，每次给定一个n(n<=2e5)，表示长为n的序列，

还有一个值k(1<=k<=1e9)，第i位的值ai(1<=ai<=k)，表示初始时第i个人的血量

每次操作，你可以选择一个区间，令这个区间的人的血量减1，

特别地，当一个人血量减到0时，会立刻恢复到k，

求最小的操作数，使得所有人的血量最终都为k

思路来源

官方题解

题解

首先，如果不带%k的操作，就是一个标准的差分，取差分数组中正项求和

环上版本：

AtCoder Regular Contest 136 C.Circular Addition(差分/环上区间减1使所有数为0的最小操作数)_Code92007的博客-CSDN博客

树上版本：

2020牛客暑期多校训练营（第十场）C.Decrement on the Tree(贪心/树上一条链减1使所有链为0的最小操作次数)_Code92007的博客-CSDN博客

%k版本：

包含了%k操作后，可以将若干个值拔高，

一次操作可以拔高k，这样可以用于后面的下降，

拔高时，加上对应的代价，下降时，无需消耗额外的代价，

首先，把读入的k变成0

然后，以官方题解，也就是第二个样例的图为例，

(i,ci)表示当前在考虑到第i个数，当前的值为ci，

ci可以加上若干倍的k，用于后面下降，可以一次加一倍的

问题等价于，需要从(0,0)走到(n+1,0)的最小代价

 根据第二个样例举例，

n=7 k=3

1 2 3 1 3 2 1

先将ai%k，然后前后各补一个0，变成

0 1 2 0 1 0 2 1 0

然后，对于下降和拔高两种操作来说，

先假设，操作是都下降，也就是找到与a[i]%k相同，且小于a[i-1]的最大的那个值

0 -2 -4 -6 -8 -9 -10 -11 -12

因为我们最后需要到0，而不是-12，所以拔高的次数是固定的4次，

固定的如何理解：

每次要么-x（下降），要么-x+k（拔高），

那么把-x求个和，求最后和0的距离，就知道需要+k几次了

都下降后，再根据实际中途操作时ai不能小于0的限制，反悔贪心拔高，

每次拔高操作，相当于将[拔高点,i]的函数曲线向上平移k个单位长度，代价是堆内最小的代价

所以，最后的操作是，

1. 能下降就下降，并把拔高（反悔）的代价丢入最小堆中

2. 需要拔高时（也就是不能再下降，再下降ai就为负值了），

此时，把当前需要拔高的值也丢入最小堆中，然后从堆中取最小的代价，进行拔高

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
const int N=2e5+10;
int T,n,k,a[N];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	sci(T);
	while(T--){
		while(!q.empty())q.pop();
		sci(n),sci(k);
		ll ans=0;
		rep(i,1,n){
			sci(a[i]);
			a[i]%=k;
			if(a[i]>=a[i-1]){
				q.push(a[i]-a[i-1]);
				ans+=q.top();
				q.pop();
			}
			else{
				q.push(k+a[i]-a[i-1]);
			}
		}
		ptlle(ans);
	}
	return 0;
}