【Codeforces】 CF1685C Bring Balance

本文主要是介绍【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 <bits/stdc++.h>
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;
}

这篇关于【Codeforces】 CF1685C Bring Balance的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---