题解：CF1970A1 Balanced Shuffle (Easy)

先计算出字符串 s 中每个字符的 Prefix balance 值。

然后先按照 Prefix balance 值从小到大排序。如果 Prefix balance 值一样，就按位置从大到小排序。

最后输出即可。

#include<iostream>//头文件
#include<algorithm>
using namespace std;
struct Node
{
    char c;//储存字符
    int id;//储存字符位置
    int pb;//储存 Prefix balance值，Prefix balance值 = 左括号数 - 右括号数
};
Node a[500005];
string s;
int k1, k2; //k1:左括号数,k2:右括号数
bool cmp(Node a, Node b){
    if(a.pb == b.pb) return a.id > b.id;//如果 Prefix balance 值一样，就按位置从大到小的规则排序
    return a.pb < b.pb;//如果 Prefix balance 值不一样，就按 Prefix balance 值从小到大排序
}
int main()
{
    cin >> s; //输入字符串
    for (int i = 0; i < s.size(); i++)
    {
        a[i].c = s[i];
        a[i].id = i+1ll;
        a[i].pb = k1 - k2; //计算cnt,并赋值
        if (s[i] == '(') k1++; //判断左括号
        if (s[i] == ')') k2++; //判断右括号
    }
    sort(a, a + s.size(), cmp); //排序
    for(int i = 0; i < s.size(); i++)
    {
        cout << a[i].c;//输出
    }
    return 0;
}

这是蒟蒻的第一篇题解，有什么不好的地方评论区建议一下吧。