作者:jostree 转载请说明出处 http://www.cnblogs.com/jostree/p/4020792.html
题目链接: zoj 3829 Known Notation
使用贪心+模拟。由于没有数字之间没有空格，因此该题有如下性质：
1.如果该字符串全部为数字，则无需操作，直接输出0。
2.连续的n个数字后面接连续的m个*，当n>m时，一定是有效的答案。从而最终的目的就是把最后的数字尽量向前移动，把最前面非法的*尽量向后移动，因此insert操作添加数字时，只需添加在最前面即可。
3.*的个数一定要小于数字的个数，因为每个*号需要消耗掉一个数字，并且首个*消耗掉2个数字。因此如果发现数字的个数比*的个数少k个，那么需要直接在字符串首添加k+1个数字。
4.如果字符串非全数字，那么结尾的数字一定要被替换成*，否则串无效。因此遇到第一个*时，直接与结尾的数字交换。
5.遍历整个串，当发现*的个数大于等于数字的个数时，直接把该位置的*与最后的数字进行替换。
代码如下：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
using namespace std;
char str[];
void solve()
{
int len = strlen(str);
int nnum = , nstar = ;
int pnum = len-;
int res = ;
int leftnum = ;
for( int i = ; i < len ; i++ )
{
if( str[i] == '*' ) nstar++;
else nnum++;
}
if( nnum == len )
{
printf("0\n");
return;
}
if( nnum - nstar <= )
{
leftnum = nstar -nnum + ;
res += leftnum;
}
for( int i = ; i < len ; i++ )
{
while( i < pnum && str[pnum] == '*') pnum--;
if( str[i] == '*' )
{
leftnum--;
if( pnum == len- && str[pnum] != '*' )
{
str[i] = str[pnum];
str[pnum] = '*';
leftnum += ;
res++;
pnum--;
}
else if( leftnum <= )
{
str[i] = str[pnum];
str[pnum] = '*';
res++;
leftnum += ;
}
}
else leftnum++;
}
printf ( "%d\n", res );
}
int main(int argc, char *argv[])
{
int T;
scanf("%d", &T);
while( T-- )
{
scanf ( "%s", str );
solve();
}
}
另附测试用例：
1***1
**1
1*1*1*
1*1*1*1
1**
1111*
1111*1
111**1
*111*
**1111*
***111111*
*1**1
*1**1*
*1111**
*1111**1
*111**11
***111
***
**1
*1*
*11
1*
*1
1** 3
3
1
1
2
0
1
1
1
2
2
3
3
1
1
1
3
4
3
2
1
1
2
2