算法设计与分析 4.5 洪尼玛与神秘信封（反悔贪心）

题目描述：

有一天洪尼玛收到一封神秘信封，信中有一个仅由“ o ”、“ x ”和“ * ”组成的字符串，并且每个“ * ”下面有两个正整数、，分别表示该“ * ”替换成“ o ”需要的代价、替换成“ x ”需要的代价。一个字符串合法需要满足以下两个条件：

1.字符串所有前缀的“ o ”的个数必须不小于“ x ”的个数；

2.字符串的“ o ”的个数必须等于“ x ”的个数；

例如" oxoxooxx "就是一个合法的字符串。洪尼玛想知道将所有的“ * ”替换成“ o ”或“ x ”使得该字符串合法的最小代价是多少？如果无解输出-1。

输入格式：

第一行为一个字符串，表示字符串；

接下来行（表示字符串中“ * ”的个数），每行两个正整数、，表示替换成“ o ”、“ x ”所需的代价；

对于60%的数据，字符串长度不大于；

对于100%的数据，字符串长度不大于，。

输出格式：

若有解，输出一个正整数，表示最小代价；若无解，输出-1。

样例输入：

o**x
1 2
3 5

样例输出:

5

解法:

这其实是一个合法括号的问题，“（”的个数要等于“）”的个数，且之前有一个“（”之后才可以有“）”，“）”总数不能比之前的“（”多。

首先将可变的‘？’全变成‘）’，然后从左往右遍历，遇到‘？’变成的‘）’就把b[i]-a[i]加入优先队列，当左括号数小于右括号时，从队列中取出b[i]-a[i]最大的，答案减掉它，相当于把‘？’变成‘(’

相当于先一刀切所有都变成“）”，然后根据条件开始一步一步“反悔”，把“）”改成“（”，最后得到答案。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#define LL long long
#define debug(x) cout << "[" << x << "]" << endl
using namespace std;

const int mx = 100001;
char s[mx];
LL a[mx], b[mx];

int main(){
    priority_queue<LL> q;
    int sum = 0;
    LL ans = 0;
    scanf("%s", s);
    int len = strlen(s);
    for (int i = 0; i < len; i++)
        if (s[i] == '*') scanf("%lld%lld", &a[i], &b[i]);
    for (int i = 0; i < len; i++){
        if (s[i] == 'o') sum++;
        else {
            sum--;
            if (s[i] == '*') {
                ans += b[i];
                q.push(b[i]-a[i]);
            }
        }
        if (sum < 0){
            if (q.empty()){
                printf("-1\n");
                return 0;
            }
            ans -= q.top();
            sum += 2;
            q.pop();
        }
    }
    if (sum != 0) printf("-1\n");
    else printf("%lld\n", ans);
    return 0;
}

恩...算法可以轻易反悔，可是人生不可以，有些事有些人，错过了就是错过了。