Codeforces Round #288 (Div. 2)E. Arthur and Brackets

贪心法。时间复杂度O(n)。

这道题关键是搞清这么几个点，代码就很好写了：

1.')'如果能紧挨着它相应的'('放，就这么紧挨着放是最优的，这一对以后就对别人没影响，完全不用再考虑了。

2.如果当前'('的右面紧挨着的那位不能放')',那么那一位必然放'('。

3.虽然都是小括号，但是括号之间相互配对的对应关系是定好的，所以应该用一个栈来保存右括号信息，只用计数器那种简单方法是不可取的。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
#include<cctype>
#include<sstream>
using namespace std;
#define pii pair<int,int>
#define LL long long int
const int eps=1e-8;
const int INF=1000000000;
const int maxn=600+10;
int n,p=0,l[maxn],r[maxn];
char s[maxn+maxn];
stack<pii>st;
int main()
{
    //freopen("in2.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        cin>>l[i]>>r[i];
        st.push(make_pair(l[i]+p,r[i]+p));
        s[p++]='(';
        while(!st.empty()&&p>=st.top().first&&p<=st.top().second)
        {
            s[p++]=')';
            st.pop();
        }
    }
    if(st.empty()) cout<<s<<endl;
    else puts("IMPOSSIBLE");
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}