传送门:Problem - 1168A - Codeforces
定义操作使得ai变成(ai+1) mod m ,求对每个数进行的操作中最大操作数的最小值,使得序列不下降
因为m<=300000,枚举必炸,考虑对单个数操作数的最大值x进行二分
check函数:
思路:我们要使得序列前面的数尽量小,这样后面的数进行的操作数更少,更有可能出现单调不下降序列,x为此函数中单个数可以进行的操作的最大值。
我们在对一个数进行操作时,使用一个变量minn记录前一个数的值,我们在第i次操作时,有如下决策:
1.如果minn<=a[i]
(1)如果a[i]+x>=m,即操作后比m值大,可以通过取模的方式使得该数变小
那么令取模后的最大值为y=(a[i]+x)%m,如果y>=minn,说明a[i]进行至多x次的操作中取值范围涵盖了minn,这时可以直接令这个数为minn使得这个数最小即minn=minn
否则取模后的数的范围无法涵盖minn,这时这个数可以取的最小值只能是a[i]即minn=a[i]
(2)如果a[i]+x<m,易知此时的最小值minn只能为a[i]
2.如果minn>a[i]
不用考虑a[i]+x>=m,此时minn大于a[i],应先满足若干次操作后a[i]大于minn,进行操作使a[i]取模变小无意义
(1)如果a[i]+x>=minn,则此时最小值minn=minn
(2)如果a[i]+x<minn,说明此时进行了操作数达到最大后仍旧无法使得序列不下降,说明x值不符合条件,直接return 0
当循环完一遍后,序列构造完毕,最大操作数为x时可以满足条件,return 1
然后对x在0到m-1范围内进行二分查找即可
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; int n,m; int a[300010]; int check(int x) { int minn=0; int flag=0; for(int i=1;i<=n;i++) { if(minn<=a[i]) { if(a[i]+x>=m) { if((a[i]+x)%m>=minn) { continue; } else minn=a[i]; } else minn=a[i]; } else if(minn>a[i]&&minn<=a[i]+x) { continue; } else if(minn>(a[i]+x)){ flag=1; break; } } return flag; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; int l=0,r=m-1,mid; while(l<r) { mid=(l+r)/2; int x=check(mid); if(x==1) { l=mid+1; } else if(x==0) { r=mid; } } cout<<r<<endl; return 0; }