526互联

abc064d <贪心/前缀和>

发布时间 2023-07-08 19:15:46作者: O2iginal

D - Insertion

另一种做法,注意这两种写法:

  1. max_element
  2. string(个数, 字符)
// https://atcoder.jp/contests/abc064/tasks/abc064_d
// 贪心
// 要求答案为字典序最小, 因而补充的 '(' 都放在最前面, ')'都放在最后面
// 从左到右遍历, 记录未匹配的左括号个数 cntl,
// 当出现右括号, 且其左侧cntl个数=0 (没有可匹配的左括号), 则pre++ (在最前面补上一个左括号);
// 若遍历结束, cntl > 0, 即仍有未匹配左括号, 则在最后补右括号
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

void solv()
{
    int n;
    string s;
    cin >> n >> s;
    int pre = 0, suf = 0, cntl = 0;
    for (auto ch: s)
    {
        if (ch == '(') cntl ++;
        else
        {
            if (cntl > 0) cntl --;
            else pre ++;
        }
    }
    suf = cntl;
    while (pre --) cout << "(";
    cout << s;
    while (suf --) cout << ")";
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}