ZOJ Problem Set - 3829Known Notation（贪心）
题目大意：给你一个后缀表达式（仅仅有数字和符号），可是这个后缀表达式的空格不幸丢失，如今给你一个这种后缀表达式，问最少须要多少操作能够把这个表达式变成合法的。
操作：
1、在这个表达式的不论什么位置插入‘’或者数字（一位数）。
2、把这个表达式的不论什么两个位置的字符对换。
解题思路:
一開始想的好复杂，结果还是漏了某种情况，一直过不去；就是卡在了碰到‘’的时候，数字不够是插入好还是替换好。
事实上仅仅要这么想：首先，数字的个数至少要是符号的个数 + 1.先求数字和符号的个数。数字不够插入自然更优，否则替换更好，而且插入数字在最越前面越好，替换‘’替换在越后面越好。
注意：所有是数字的情况。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1005;
char str[maxn];
int main () {
int T;
scanf ("%d", &T);
while (T--) {
scanf ("%s", str);
int num, op, ans;
int len = strlen (str);
ans = num = op = 0;
for (int i = 0; i < len; i++)
if (str[i] == '*')
op++;
num = len - op;
if (!op) {
printf ("0
");
continue;
}
if (str[len - 1] != '*') {
ans++;
for (int i = 0; i < len; i++)
if (str[i] == '*') {
swap(str[i], str[len - 1]);
break;
}
}
int cnt = 0;
for (int i = 0; i < len; i++) {
if (str[i] == '*') {
if (cnt > 1)
cnt--;
else {
if (num >= op + 1) {
for (int j = len - 1; j >= 0; j--)
if (str[j] != '*') {
swap(str[j], str[i]);
cnt++;
ans++;
break;
}
} else {
ans++;
num++;
if (!cnt) {
i--;
cnt = 1;
}
}
}
} else
cnt++;
}
printf ("%d
", ans);
}
return 0;
}