【Codeforces】 CF1685C Bring Balance

题目链接

CF方向
Luogu方向

题目解法

首先观察数据可以发现答案 $\le 2$（别问我怎么发现的
首先判掉 $ans=0$ 的情况

考虑 $ans=1$ 的情况（下面把 $n$ 当做 $n\ast 2$）
把 $($ 当成 $1$，$)$ 当成 $-1$，令 $s_i$ 为其前缀和
那么首先可以找到最小的 $s_i<0$ 的 $i$ 和最大的 $s_n-s_{i-1}<0$ 的 $i$，可以发现 $s_n=0$，所以需要找到第一个和最后一个满足 $s_i<0$ 的 $i$，令其分别为 $L,R$
那么一个合法的操作区间 $[l,r]$ 需要满足 $L\le l\le r\le R$
考虑 $[1,l-1]$ 和 $[r+1,n]$ 的前缀和一定 $\ge 0$
现在考虑 $[l,r]$ 中 $i$ 位置的前缀和会变成什么？即为 $s_r-s_{i-1}+s_{l-1}$
所以我们的目标是找到 $[1,L]$ 中最大的 $s_{l-1}$ 的 $l$ 以及 $[R,n]$ 中最大的 $s_r$ 的 $r$，直接判断是否合法即可

考虑 $ans=2$ 的情况
我们只要找到最大 $s_i$ ，交换 $[1,i]$ 和 $[i+1,n]$ 即可
为什么？
考虑对于 $x\in [1,i]$，$s_x$ 会变成 $s_i-s_{x-1}$，因为 $s_i$ 最大，所以这个值一定 $\ge 0$
对于 $x\in [i+1,n]$，同理 $s_x$ 会变成 $s_n-s_{x-1}+s_i=s_i-s_{x-1}\ge 0$

时间复杂度 $O(n)$

#include 
using namespace std;
const int N=200100;
int n,pref[N];
char str[N];
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
bool check(){
	int s=0;
	for(int i=1;i<=n;i++){
		if(str[i]=='(') s++;
		else s--;
		if(s<0) return false;
	}
	return true;
}
void work(){
	n=read();n<<=1;
	scanf("%s",str+1);
	for(int i=1;i<=n;i++){
		if(str[i]=='(') pref[i]=pref[i-1]+1;
		else pref[i]=pref[i-1]-1;
	}
	if(check()){ puts("0");return;}
	int L,R;
	for(int i=1;i<=n;i++) if(pref[i]<0){ L=i;break;}
	for(int i=n;i;i--) if(pref[n]-pref[i-1]>0){ R=i;break;}
	int mxr=R,mnl=L-1;
	for(int i=R+1;i<=n;i++) if(pref[i]>pref[mxr]) mxr=i;
	for(int i=0;i<L;i++) if(pref[i]>pref[mnl]) mnl=i;
    mnl++;
	reverse(str+mnl,str+mxr+1);
	if(check()){
		puts("1");printf("%d %d\n",mnl,mxr);
		return;
	}
	int mxp=1;
	for(int i=2;i<=n;i++) if(pref[i]>pref[mxp]) mxp=i;
	puts("2");printf("%d %d\n%d %d\n",1,mxp,mxp+1,n);
}
int main(){
	int T=read();
	while(T--) work();
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51