CF1168 A. Increasing by Modulo

题目传送门：https://codeforces.com/problemset/problem/1168/A

题目大意：
给定一串长度为\(n\)的序列\(A\)，每次操作可以选取任意\(k\)个数\(i_1,i_2,...,i_k\)，满足\(1\leqslant i_1，使\(A_{i_j}\)变为\((A_{i_j}+1)\%m\)

问最少多少次操作后，可以使序列\(A\)变为单调不降序列

考虑二分操作数\(\alpha\)，因为每次可以选取任意个数进行操作，所以每个数的操作次数都是 \(0\sim \alpha\) 且相互独立。

我们可以记录上一个数的值 \(Last\) ，显然\(Last\)越小答案不会更劣，对当前的\(A_i\)而言：

如果\(A_i\leqslant Last\leqslant A_i+\alpha\)，我们可以直接将\(A_i\)加到\(Last\)即可
如果\(A_i>Last\) 且 \((A_i+\alpha)\%m\geqslant Last\)，我们也可以将\(A_i\)加到\(Last\)
如果\(A_i>Last\) 且 \((A_i+\alpha)\%m，那我们就不对\(A_i\)操作
如果\(A_i 且 \(A_i+\alpha，那无论怎么操作都不可行

故直接参考上述条件二分答案即可

/*program from Wolfycz*/
#include
#include
#include
#include
#include
#include
#include
#define Fi first
#define Se second
#define ll_inf 1e18
#define MK make_pair
#define sqr(x) ((x)*(x))
#define pii pair
#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++;
}
templateinline 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;
}
templateinline 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>1;
		if (Check(mid))	r=mid-1;
		else	l=mid+1;
	}
	printf("%d\n",r+1);
	return 0;
}

OJCodeforces 其他二分答案

CF1168 A. Increasing by Modulo

相关

标签