http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3829

现场做这道题的时候，感觉是思维题。自己智商不够。不敢搞，想着队友智商好，他们搞吧。可是没出来这题......

以后不论什么时候，都自信点....该想的还是好好自己想，这类题感觉就是先去找性质，然后一点点找规律，假设必要的话。自己提出一点猜想。然后假设自己举不出来反例，就临时觉得是正确的

下午搞了一下午。发现还是悲剧，晚上參考了两个题解

http://blog.csdn.net/keshuai19940722/article/details/40039975

事实上至少能够总结出来一下规律：

1、必须num(*)<num(数字)

2、前面全是数字的后面全是*是合法的。就是说，假设须要交换的话，能够把*全换到最后，就是把*和最后的数字交换位置，反正每次耗费都是1

3、由于交换一次耗费为1，插入一次耗费也是1，所以假设不满足规律1，能够先插入，又由于规律2，所以把数字在一開始就所有插入到最前面，用栈模拟后缀表达式的验证过程，假设缺数字。就把最后的数字和当前的*交换位置，根据是规律2.不会缺星号的。由于连续的数字能够当做同一个数字

以上三条足够解决这个问题

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

const int MAXN = 1000+50;

#define CL(a,b) memset(a,b,sizeof(a))

#define ll long long

#define ull unsigned long long

#define IN(s) freopen(s,"r",stdin)

char str[MAXN],sta[MAXN*10];

int pos[MAXN*10];

int len,numa,numb,tp,postp;

void init()

{

    tp=postp=0;

    numa=numb=0;//

    scanf("%s",str);

    len=strlen(str);

}

ll solve()

{

    for(int i=0;i<len;i++)

    {

        if(str[i] == '*')

            numa++;

        else

        {

            numb++;

            pos[postp++]=i;

        }

    }

    if(numa == 0)return 0;//****特判

    ll ans=0;

    tp=max(numa+1-numb,0);//假设数字多。总是能够组合出来的

    //在开头补上数字

    ans=(ll)tp;

    for(int i=0;i<len;i++)

    {

        if(str[i] == '*'){

            if(tp>=2)tp--;

            else{

                str[pos[postp-1]]='*';

                postp--;

                tp++;

                ans++;//交换没有强调相邻

            }

        }

        else

            tp++;

    }

    if(ans==0 && str[len-1]!='*')ans++;//

    return ans;

}

int main()

{

    //IN("K.txt");

    int ncase;

    scanf("%d",&ncase);

    while(ncase--)

    {

        init();

        printf("%lld\n",solve());

    }

    return 0;

}