题解：AT_cpsco2019_s2_c Delicious Burgers

· · 题解

题目传送门

题目简述

如果一个只由 ( 和 ) 组成的字符串，每个 ( 都能 找到与之匹配的 )，且不能重复匹配同一个 ( 或 )，则称为 bun string。

现在要求在 bun string S 中插入 k 个字符 |，| 与 | 之间不能相邻，以创建汉堡字符串，这个汉堡字符串的美味程度等于每个 | 外套了几层小括号之和。求这个汉堡字符串的最大美味程度。

主要思路

要求最大美味程度，说明每个 | 要尽量向括号的最深处插入。那么就可以创建一个优先队列，存储遍历 S_{1} \sim S_{n} 时当前处在第几层括号。最后重复执行 k 次，由于优先队列自动从大到小排序，将答案每次增加队列顶，然后弹出队列顶即可。

时间复杂度

O(n \log n)

最最后：十年 OI 一场空，____。

AC Code

#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
void print(ll x){if(x<0){putchar('-');x=-x;}if(x>9){print(x/10);}putchar(char(x%10+'0'));}
void print(int x){if(x<0){putchar('-');x=-x;}if(x>9){print(x/10);}putchar(char(x%10+'0'));}
void print(string s){int n=s.length();for(int i=0;i<n;i++)putchar(s[i]);}
inline int read_int() {int f=1,x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline ll read_ll() {int f=1;ll x=0;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline string read_str(){string x="";char ch=getchar();while(ch==' '||ch==' '||ch=='\n'||ch=='\r')ch=getchar();while(ch!=' '&&ch!=' '&&ch!='\n'&&ch!='\r'){x+=ch;ch=getchar();}return x;}
// ----------------------------

// ----------------------------
priority_queue<int> q;
// ----------------------------

int main() {
    int n = read_int();
    int k = read_int();
    string s = read_str();
    // ------------------------
    int depth = 0;
    for (int i=0;i<n;i++) {
        if (s[i] == '(') depth++;
        else depth--;
        q.push(depth);
    }
    ll ans = 0;
    for (int i=1;i<=k;i++) {
        if (q.empty()) break;
        ans += q.top();
        q.pop();
    }
    // ------------------------
    print(ans);
    return 0;
}