题目的意思是一个人记录罪犯进出的过程,"("代表进去,")"代表出去,“?”代表没记录到。问你是否存在这么一种可能,把问号变为"("或")",保证开始和结束后房间里面都没有人。


贪心即可,记录前缀和,然后判断,之后不断修改"?"再进行判断,保证“)”不能多。


地址:http://codeforces.com/gym/101149/problem/H


代码:

StatusAccepted
Time31ms
Memory2544kB
Length1040


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=500005;
char s[maxn];
int main()
{
    while(~scanf("%s", &s)){
        int len=strlen(s);
        int num=0, g=0, ans=1;
        for(int i=0;i<len;i++){
            if(s[i]=='?')g++;
            else if(s[i]=='(')num++;
            else num--;
        }
        if(abs(num)>g||int(g-abs(num))%2){
            ans=0;
        }
        else{
            int bu=(g-num)/2;
            num=0;
            for(int i=0;i<len;i++){
                if(s[i]=='?'){
                    if(bu){
                        s[i]='(';
                        bu--;
                    }
                    else s[i]=')';
                }
                if(s[i]=='(')num++;
                else num--;
                if(num<0){
                    ans=0;
                    break;
                }
            }
        }
        if(ans){
            printf("%s\n", s);
        }
        else printf("Impossible\n");
    }
    return 0;
}