D

给你一个长度为n的括号序列,然后你可以选择交换两个位置,你需要使得能够变成 合法括号序列的起点最多。

题解

  1. 人尽皆知的东西:合法的括号序列是,令'('为1,')'为-1,那么前缀和需要>=0,且最后的总和应该为0.

  2. 假设现在已经是交换好的序列了,那么答案个数,就是前缀和的最小值的个数。这是因为最小值,例如最小值-1(或者-2),造成这个-1(或者-2)原因就是前面的没有一个1(或者2),那我们就得把前面的-1-2放到后面去,意思就是将最小值的后面第一段作为起点

  3. 如果交换'('和')',会使得这个区间的每个数的前缀和-=2,不包括交换点。如果交换')'和'(',你可以改变交换为a[i]和a[j+n],将其变成交换'('和')'

  4. 因为我们使得这个区间里面的每个数都减去了2,那么最小值只可能是 区间内的2+区间外的0,或者区间内的1。

所以我们看两种情况,哪种最小即可

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int n;
string s;
int a[maxn],ps[maxn];
int main(){
cin>>n>>s;
for(int i=0;i<s.size();i++){
int p = i+1;
if(s[i]=='('){
a[p]=a[p+n]=1;
}else{
a[p]=a[p+n]=-1;
}
}
for(int i=1;i<=2*n;i++){
ps[i]=ps[i-1]+a[i];
}
if(ps[n]){
cout<<"0"<<endl;
cout<<"1 1"<<endl;
return 0;
}
int beg = min_element(ps+1,ps+1+n)-ps;
int minv = ps[beg];
for(int i=1;i<=2*n;i++){///所有值减去最小值,也就是最低也是从0开始
ps[i]-=minv;
}
int cl = -1, cc = 0;
int mx = 0,ansl = 1,ansr = 1;
int cl2 = 0, cc2 = 0;
int mx2 = 0, ans2l = 1, ans2r = 1;
for(int i=1;i<=n;i++){
if(ps[i+beg]==1){
if(cc>mx){
mx=cc;
ansl=cl,ansr=i;
}
cl=i+1;///这是因为我们遇到的是1,而选择位置3和位置8交换影响的是3 4 5 6 7;
///所以ans1=i+1;ansr=i;
cc=0;
}else if(ps[i+beg]==2)++cc;
///上面这部分表示的是区间里全都是大于等于2的这样减2才可以保证最低的值是0;然后再到下面统计区间外的0;
///同时第一个2肯定是从1进去,最后一个2肯定碰到1,所以上面的if来判断边界 if(ps[i+beg]==0){
if(cc2>mx2){
mx2=cc2;
ans2l=cl2+1,ans2r=i;
}
cl2=i;
cc2=0;
}else if(ps[i+beg]==1)++cc2;
}
for(int i=1;i<=n;i++){
if(ps[i+beg]==0)++mx;///刚开始懵逼万一有的0是我们区间统计2里面的0怎么办呢,然后想一下哦对哦区间2统计的是区间内全是大于等于2的不可能出现0,所以就是区间全大于等于2的-2变为0后+上区间外的0,和区间内的全为1再-2等于-1的比较
}
if(mx2>mx){
mx=mx2;
ansl=ans2l;
ansr=ans2r;
}
cout<<mx<<endl;
cout<<(ansl+beg-1+n)%n+1<<" "<<(ansr+beg-1+n)%n+1<<endl;
}

  

最新文章

  1. JavaScript—从数组的indexOf方法深入——Object的Property机制。
  2. php js数组问题
  3. Excel Interior.ColorIndex色彩列表
  4. 剑指Offer:面试题20——顺时针打印矩阵(java实现)
  5. linux标准daemon编写方式
  6. Python 统计IIS日志行数
  7. windows win7 win10 多系统启动菜单 多系统引导设置
  8. 查看Oracle执行计划的几种方法
  9. 【C#】Entity Framework 增删改查和事务操作
  10. .NET MVC4 实训记录之一(引入Unity3.0 Ioc框架)
  11. 一款可定制的外国jQuery图表插件jqplot
  12. PHP 领域模型与数据库映射文章
  13. PeopleRank
  14. C++中的虚函数表是什么时期建立的?
  15. Paper Reading: Stereo DSO
  16. 浅析Tomcat、JBOSS、WebSphere、WebLogic、Apache
  17. hdu1937 二维尺取
  18. Selenium2+python自动化38-显式等待(WebDriverWait)
  19. 使用JavaMail发送邮件-no object DCH for MIME type multipart/mixed报错解决
  20. 获取不到offsetHeight问题

热门文章

  1. Lesson 9 Royal espionage
  2. hdu 1541 Stars 统计&lt;=x的数有几个
  3. 十三、$.ajax、模态/非模态框、window.open()、href属性、submit()等提交请求优劣及问题解决方法
  4. [Codeforces #608 div2]1271C Shawarma Tent
  5. Day1-D-CF-1144C
  6. Pycharm 报错 Environment location directory is not empty 解决
  7. 079、Java数组之数组的静态初始化
  8. JuJu团队1月3号工作汇报
  9. bugku love
  10. PHP-WebShell-Bypass-WAF