计蒜之道2019 复赛 E.撑起信息安全“保护伞” 贪心+构造

题意：给出一个括号序列，求它的前驱和后继。

 

首先是求前驱，显然我们必须要将一个‘(’向前移动，那么必然是将')('交换成'()'。

在这个条件下，我们可以发现应该是从后往前找到第一个这样可以交换的地方，对其进行交换，而前面的不变，后面的则将其贪心地置为')...'+'()()()..'的形式，这样的形式字典序显然是最大的。

举个例子‘((())()(()))’

第一步 找到可以交换的地方‘((())()(()))’

第二步 将后面的序列转换成字典序最大的形式 ((())(()))()’

 

然后是求后继，这个和求前驱其实是差不多的，不过变成是把'()'交换成‘)(’。

这个时候就不能找到一个就去直接交换了 ，因为这样可能会导致括号序列不合法，需要稍微做一下判断。

然后后续贪心地置为'((((....'+'))))....'的形式。

 

代码：

#include<bits/stdc++.h>
using namespace std;
int i,i0,n,m;
char s[1000005];
int main()
{
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(i=len-2;i;i--)
    {
        if(s[i]==')'&&s[i+1]=='(')
        {
            for(i0=1;i0<i;i0++)printf("%c",s[i0]);
            printf("()");
            int cnt0=0,cnt1=0;
            for(i0=i+2;i0<=len;i0++)
            {
                if(s[i0]=='(')cnt0++;
                else cnt1++;
            }
            while(cnt0<cnt1)printf(")"),cnt1--;
            while(cnt0&&cnt1)printf("()"),cnt0--,cnt1--;
            printf("\n");
            break;
        }
    }
    int cnt=1;
    if(s[len-1]==')')cnt++;
    else cnt--;
    for(i=len-2;i;i--)
    {
        if(cnt>1&&s[i]=='('&&s[i+1]==')')
        {
            for(i0=1;i0<i;i0++)printf("%c",s[i0]);
            printf(")(");
            int cnt0=0,cnt1=0;
            for(i0=i+2;i0<=len;i0++)
            {
                if(s[i0]=='(')cnt0++;
                else cnt1++;
            }
            while(cnt0)printf("("),cnt0--;
            while(cnt1)printf(")"),cnt1--;
            printf("\n");
            break;
        }
        if(s[i]=='(')cnt--;
        else cnt++;
    }
    return 0;
}