首页 > 代码库 > ZOJ Problem Set - 3829Known Notation(贪心)

ZOJ Problem Set - 3829Known Notation(贪心)

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;
}

ZOJ Problem Set - 3829Known Notation(贪心)