Treasure 题解

xvl- / 2023-08-05 / 原文

题目传送门

一道贪心题。

贪心策略是除了最后一个 # 其他的都变成 \(1\) 个 )，这样前面的 ) 就尽可能的少，最后的 # 变成的 ) 数量加上前面的 ) 数量等于 ( 的数量，这样在最后所有的括号都会匹配。最后检查一下合不合法。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
string s, tmp;
int sum1, sum2, sum3, sum4, cnt, last; // sum1 和 sum2 用来判断最后一个 # 要变成多少个 )
signed main() {
    ios :: sync_with_stdio(0);
    cin >> s;
    if (s.size() == 1) {
        cout << -1;
        return 0;
    } // 如果只有 1 个字符必然无解
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == '#') {
            cnt++;
            last = i;
            break;
        }
    }
    for (int i = 0; i < s.size(); i++) {
        if (i == last) continue; // 最后一个 # 先不处理
        if (s[i] == '(') sum1++; 
        else if (s[i] == ')') sum2++;
        else {
            cnt++;
            s[i] = ')';
            sum2++;
        }
    }
    if (sum1 == sum2) {
        cout << -1;
        return 0;
    } // 必然无解，因为 # 必须变成 1 个以上的 )
    for (int i = 1; i <= sum1 - sum2; i++) tmp += ')';
    s.replace(last, 1, tmp);
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') sum3++;    
        if (s[i] == ')') sum4++;
        if (sum4 > sum3) {
            cout << "-1";
            return 0;
        }
    } // 判断是否合法
    for (int i = 1; i <= cnt; i++) {
        if (i == cnt) cout << sum1 - sum2;
        else cout << 1 << "\n"; 
    } // 贪心策略
    return 0;
}