题解：AT_arc120_d [ARC120D] Bracket Score 2

Elairin176 · 2025-01-11 15:53:07 · 题解

Link
小水题，不知道为什么 kenkoooo 给了 1996 的 rating。

题意

定义一个长度为 2n 的括号序列 s 的价值为：

其中 (u_i,v_i) 表示 s 中一对匹配括号的位置。
最大化价值。

解法

我们拆开绝对值后易得：a 的前 n 小一定作为负贡献出现，前 n 大一定作为正贡献出现。
那么我们就确定了符号，接下来考虑分配括号。
同样显然地，一对匹配的括号两端一定是异号贡献，依据这个我们直接用 set 维护即可。
复杂度 \mathcal{O}(n\log n)。
CODE：

//luogu paste jo5j6ogx
cst int N=4e5;
int n;
struct node{
    int x,p;
}a[N+10];
bool ans[N+10],f[N+10];
set<int>s1,s2;
int main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    n=read<int>();
    for(int i=1;i<=(n<<1);i++){
        a[i].x=read<int>();
        a[i].p=i;
    }
    sort(a+1,a+1+(n<<1),[](cst node&x,cst node&y){ret x.x<y.x;});
    for(int i=1;i<=n;i++) f[a[i].p]=1;
    for(int i=1;i<=(n<<1);i++){
        if(f[i]){
            if(s2.empty()) s1.insert(i);
            else{
                auto p=s2.end();p--;
                ans[i]=1;
                s2.erase(p);
            }
        }else{
            if(s1.empty()) s2.insert(i);
            else{
                auto p=s1.end();p--;
                ans[i]=1;
                s1.erase(p);
            }
        }
    }
    for(int i=1;i<=(n<<1);i++){
        if(ans[i]) pc(')');
        else pc('(');
    }
    ret 0;
}

record(atcoder)