CF1169C. Increasing by Modulo（二分）

linkkkkk
题意：
给出 n , k n,k n,k和数组 a a a，每次都可以选出若干个元素让他们的值变成 ( a i + 1 ) m o d    k (a_i+1)\mod k (ai​+1)modk
问最少需要几次操作才能使得数组非递减
思路：
操作次数是有单调性的，比如当 x x x次可以成功的话， x + 1 x+1 x+1次也可以成功，最后一次可以调整最大或最小元素。考虑二分答案。
对于 c h e c k check check，贪心的考虑，如果 b i = = b i − 1 b_i==b_{i-1} bi​==bi−1​，跳过；如果 b i > b i − 1 b_i>b_{i-1} bi​>bi−1​，已经满足要求了，为了有利于后面的操作，尽可能的让 b i = b i − 1 b_i=b_{i-1} bi​=bi−1​，所需要的操作次数为 b [ i − 1 ] + k − b [ i ] b[i-1]+k-b[i] b[i−1]+k−b[i]；如果 b i < b i − 1 b_i<b_{i-1} bi​<bi−1​，那么 b i b_i bi​一定要增大，跟 b i − 1 b_{i-1} bi−1​相等就可以了，所需要的操作次数为 b [ i − 1 ] − b [ i ] b[i-1]-b[i] b[i−1]−b[i]，如果 b [ i − 1 ] − b [ i ] < m i d b[i-1]-b[i]<mid b[i−1]−b[i]<mid的话说明次数是不可行的，直接返回 f a l s e false false。
代码:

// Problem: C. Increasing by Modulo
// Contest: Codeforces - Codeforces Round #562 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1169/C
// Memory Limit: 256 MB
// Time Limit: 2500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;

int n,k,a[300007],b[300007];

bool check(int mid){
	for(int i=1;i<=n;i++) b[i]=a[i];
	for(int i=1;i<=n;i++){
		if(b[i]<b[i-1]){
			if(b[i-1]-b[i]>mid) return 0;
			b[i]=b[i-1];
		}
		else{
			if(b[i-1]+k-b[i]<=mid) b[i]=b[i-1];
		}
	}
	return 1;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=0,r=k,ans;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout<<ans<<endl;
	return 0;
}