linkkkkk
题意：
给出n , k和数组a，每次都可以选出若干个元素让他们的值变成k( a i + 1 ) m o d
问最少需要几次操作才能使得数组非递减
思路：
操作次数是有单调性的，比如当x次可以成功的话，x + 1次也可以成功，最后一次可以调整最大或最小元素。考虑二分答案。
对于c h e c k，贪心的考虑，如果b i = = b i − 1，跳过；如果b i > b i − 1，已经满足要求了，为了有利于后面的操作，尽可能的让b i = b i − 1，所需要的操作次数为b [ i − 1 ] + k − b [ i ]；如果b i < b i − 1
相等就可以了，所需要的操作次数为b [ i − 1 ] − b [ i ]，如果b [ i − 1 ] − b [ i ] < m i d
代码:
// 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; }
