首页 > 代码库 > #282(div2) C. Treasure

#282(div2) C. Treasure

题意:#可以变换成>=1个‘)‘,问每个#可以变换成多少个‘)‘。使得整个字符串正常,否则输出-1。

思路:我们可以先把可以消掉的()消掉,再判断下比如#在新的字符串最前面或者(在最后面是不行的,然后我们让前面的#都变成一个),那么最后一个可以变成剩下的。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int b[100005];
 5 int main(){
 6     string s;
 7     cin>>s;
 8     int l=0;
 9     if(s[l]==)||s[s.size()-1]==() {
10         cout<<-1<<endl;return 0;
11     }
12     int s1=0,s2=0,s3=0;
13     for(int i=0;i<s.size();i++){
14         if(s[i]==() {
15             b[l++]=i;
16             s1++;
17         }
18         else if(s[i]==)) {
19                 s2++;
20                 l--;
21                 if(l==-1) {
22                     printf("-1\n");return 0;
23                 }
24                 s[b[l]]=%;s[i]=%;s3++;
25         }
26     }
27     int s4=s.size()-s1-s2;
28     s1-=s3;
29     if(s1<s4){
30         cout<<-1<<endl;return 0;
31     }
32     int sum=0;
33     for(int i=s.size();i>=0;i--){
34         if(s[i]==() {
35             cout<<-1<<endl;return 0;
36         }
37         else if(s[i]==#) {
38                 l=i;
39                 break;
40         }
41     }
42     for(int i=0;i<s.size();i++){
43         if(s[i]==() {
44             break;
45         }
46         else if(s[i]==#) {
47                cout<<-1<<endl;return 0;
48         }
49     }
50     for(int i=0;i<s.size();i++){
51             if(s[i]==() sum++;
52             else if(s[i]==#){
53                     if(i!=l)
54                    cout<<1<<endl;
55                     else
56                     {
57                         cout<<sum<<endl;break;
58                     }
59                    sum--;
60             }
61     }
62 }

 

#282(div2) C. Treasure