【Codeforces Round #551 (Div. 2) C. Serval and Parenthesis Sequence(Java版)

题目链接：http://codeforces.com/contest/1153/problem/C
题目大意：要求前缀里面不能有正确的表达式，但整个字符串是正确的表达式，构造括号表达式，优先放(，构造完之后验证是否符合。这是我第一次打cf比赛，因为cf太晚了。这题当时没做出来，后来补的题，有点贪心的感觉。
具体思想在代码中

ac代码：

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
//构造括号表达式，优先放(
//要求前缀里面不能有正确的表达式，但整个字符串是正确的表达式
public class Main {
	public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		String a=sc.next();
		char ctr[]=a.toCharArray();
		if(n%2!=0||ctr[0]==')'||ctr[n-1]=='('){//奇数不可能匹配，首尾必须分别为'(' ')'
			System.out.println(":(");
			return;
		}
		int l=0,r=0;
		for(int i=0;i<n;i++){
			if(ctr[i]=='(') //已有的左括号数量
				l++;
			if(ctr[i]==')') //已有的右括号数量
				r++;
			if(l>n/2||r>n/2){
				System.out.println(":(");
				return;
			}
		}
		l=n/2-l;//需要让？变成(的数量
		for(int i=0;i<n;i++){
			if(ctr[i]=='?'&&l!=0){ //先填左括号
				ctr[i]='(';
				l--;
			}else if(ctr[i]=='?'){ //左括号填完填右括号
				ctr[i]=')';
				r++;
			}
		}
		l=0;
		for(int i=0;i<n;i++){
			if(ctr[i]=='(')l++;
			if(ctr[i]==')')l--;
			if(l<0||(l==0&&i!=n-1)){//如果右括号的数量大于左括号的数量在前k个中，说明真前缀匹配了
									//如果左右括号的数量相等但是并没有读到字符串的最后一位，说明真前缀也匹配了
				System.out.println(":(");
				return;
			}
		}
		if(l>0){//如果遍历完还有左括号剩余，说明整个字符串不能匹配。
			System.out.println(":(");
		}else{
			for(int i=0;i<n-1;i++){
				out.print(ctr[i]);  //刚开始直接用syso输出，好像输出量太大，直接tle了，然后用了PrintWriter187ms过了
									//差点心态爆炸
			}
			out.flush();
			System.out.println(ctr[n-1]);
		}
		sc.close();
	}
}