题目传送门:https://codeforces.com/problemset/problem/1168/A
题目大意:
给定一串长度为(n)的序列(A),每次操作可以选取任意(k)个数(i_1,i_2,...,i_k),满足(1leqslant i_1<i_2<...<i_kleqslant n),使(A_{i_j})变为((A_{i_j}+1)\%m)
问最少多少次操作后,可以使序列(A)变为单调不降序列
考虑二分操作数(alpha),因为每次可以选取任意个数进行操作,所以每个数的操作次数都是 (0sim alpha) 且相互独立。
我们可以记录上一个数的值 (Last) ,显然(Last)越小答案不会更劣,对当前的(A_i)而言:
- 如果(A_ileqslant Lastleqslant A_i+alpha),我们可以直接将(A_i)加到(Last)即可
- 如果(A_i>Last) 且 ((A_i+alpha)\%mgeqslant Last),我们也可以将(A_i)加到(Last)
- 如果(A_i>Last) 且 ((A_i+alpha)\%m<Last),那我们就不对(A_i)操作
- 如果(A_i<Last) 且 (A_i+alpha<Last),那无论怎么操作都不可行
故直接参考上述条件二分答案即可
/*program from Wolfycz*/
#include<map>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(x) ((x)*(x))
#define pii pair<int,int>
#define int_inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline char gc(){
static char buf[1000000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>inline T frd(T x){
int f=1; char ch=gc();
for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
template<typename T>inline T read(T x){
int f=1; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x<0) putchar('-'),x=-x;
if (x>9) print(x/10);
putchar(x%10+'0');
}
const int N=3e5;
int A[N+10],n,m;
bool Check(int x){
int Now=0;
for (int i=1;i<=n;i++){
if (A[i]==Now) continue;
if (A[i]>Now){
if (A[i]+x<m||(A[i]+x)%m<Now)
Now=A[i];
continue;
}
if (A[i]+x<Now) return 0;
}
return 1;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read(0),m=read(0);
for (int i=1;i<=n;i++) A[i]=read(0);
int l=0,r=m;
while (l<=r){
int mid=(l+r)>>1;
if (Check(mid)) r=mid-1;
else l=mid+1;
}
printf("%d
",r+1);
return 0;
}