Known Notation括号匹配类问题（2014年ACM/ICPC 亚洲区域赛牡丹江）

题意：

给你数字或 * 的串，你可以交换一个*和数字、在最前面添1、在一个地方插入*，问你使串满足入栈出栈的（RNP）运算法则。

思路：

引用：https://blog.csdn.net/u011580493/article/details/40077119

由于一个 * 能消除2个数字，然后生成一个数字。因此首先要保证数字个数大于等于 ‘*’ 个数+1。

如果数字个数不够，就在最前面添加。

然后开始从头开始遍历，遇到*就看当前的数字个数是否有两个或以上.不够的话，从最后面开始找第一个不是‘*’的进行交换；够则直接消掉。

从后往前找数字一定是最优的。

  1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
  2 #include <cstdio>//sprintf islower isupper
  3 #include <cstdlib>//malloc  exit strcat itoa system("cls")
  4 #include <iostream>//pair
  5 #include <fstream>//freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin);
  6 #include <bitset>
  7 //#include <map>
  8 //#include<unordered_map>
  9 #include <vector>
 10 #include <stack>
 11 #include <set>
 12 #include <string.h>//strstr substr
 13 #include <string>
 14 #include <time.h>//srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
 15 #include <cmath>
 16 #include <deque>
 17 #include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
 18 #include <vector>//emplace_back
 19 //#include <math.h>
 20 //#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
 21 #include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
 22 using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
 23 #define fo(a,b,c) for(register int a=b;a<=c;++a)
 24 #define fr(a,b,c) for(register int a=b;a>=c;--a)
 25 #define mem(a,b) memset(a,b,sizeof(a))
 26 #define pr printf
 27 #define sc scanf
 28 #define ls rt<<1
 29 #define rs rt<<1|1
 30 typedef long long ll;
 31 void swapp(int &a,int &b);
 32 double fabss(double a);
 33 int maxx(int a,int b);
 34 int minn(int a,int b);
 35 int Del_bit_1(int n);
 36 int lowbit(int n);
 37 int abss(int a);
 38 //const long long INF=(1LL<<60);
 39 const double E=2.718281828;
 40 const double PI=acos(-1.0);
 41 const int inf=(1<<30);
 42 const double ESP=1e-9;
 43 const int mod=(int)1e9+7;
 44 const int N=(int)1e6+10;
 45 
 46 char s[N];
 47 
 48 int main()
 49 {
 50 //    freopen("C:\Users\13606\Desktop\草稿.txt","r",stdin);
 51     int T;
 52     sc("%d",&T);
 53     while(T--)
 54     {
 55         int l;s[0]='$';
 56         sc("%s",s+1);
 57         l=strlen(s)-1;
 58         int cnt1=0,cnt0=0;
 59         fo(i,1,l)
 60         {
 61             if(s[i]=='*')
 62                 cnt0++;
 63             else
 64                 cnt1++;
 65         }
 66         int cnt=max(0,cnt0+1-cnt1);
 67         int ans=cnt;
 68         int pos=l;
 69         fo(i,1,l)
 70         {
 71             if(s[i]!='*')
 72                 cnt++;
 73             else
 74             {
 75                 if(cnt-1<1)
 76                 {
 77                     while(s[pos]!='*')
 78                         pos--;
 79                     swap(s[pos],s[i]);
 80                     ans++;
 81                     cnt++;
 82                 }
 83                 else
 84                     cnt--;
 85             }
 86         }
 87         pr("%d
",ans);
 88     }
 89     return 0;
 90 }
 91 
 92 /**************************************************************************************/
 93 
 94 int maxx(int a,int b)
 95 {
 96     return a>b?a:b;
 97 }
 98 
 99 void swapp(int &a,int &b)
100 {
101     a^=b^=a^=b;
102 }
103 
104 int lowbit(int n)
105 {
106     return n&(-n);
107 }
108 
109 int Del_bit_1(int n)
110 {
111     return n&(n-1);
112 }
113 
114 int abss(int a)
115 {
116     return a>0?a:-a;
117 }
118 
119 double fabss(double a)
120 {
121     return a>0?a:-a;
122 }
123 
124 int minn(int a,int b)
125 {
126     return a<b?a:b;
127 }