首页 > 代码库 > #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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。