[CF508E] Arthur and Brackets

贪心解决就行了。

用栈模拟这个过程，每次优先解决栈顶的括号。

可以看出优先解决栈顶的元素更有利于匹配上每一对括号。

 1 #include<cstdio>
 2 
 3 int n;
 4 
 5 class stack
 6 {
 7     private:
 8         int tp;
 9         int a[605];
10     public:
11         void push(int v)
12         {
13             a[++tp]=v;
14         }
15         int top()
16         {
17             return a[tp];
18         }
19         void pop()
20         {
21             tp--;
22         }
23         bool empty()
24         {
25             return tp==0;
26         }
27 };
28 
29 stack s;
30 char ans[1205];
31 int l[605],r[605],p[605],cnt;
32 
33 int main()
34 {
35     scanf("%d",&n);
36     int cnt=0,fl=1;
37     for(int i=1;i<=n;i++)
38     {
39         scanf("%d%d",&l[i],&r[i]);
40         s.push(i);
41         p[i]=cnt;
42         ans[++cnt]='(';
43         while(!s.empty())
44         {
45             int np=s.top();
46             if(r[np]+p[np]<cnt)
47             {
48                 fl=0;
49                 break;
50             }
51             if(l[np]+p[np]>cnt)break;
52             ans[++cnt]=')';
53             s.pop();
54         }
55     }
56     if(fl&&s.empty())printf("%s",ans+1);
57     else printf("IMPOSSIBLE");
58     return 0;
59 }