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\n"); 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\n", ans); } return 0; }转载于:https://www.cnblogs.com/bhlsheji/p/4376191.html
相关资源：数据结构—成绩单生成器