ARC120D Bracket Score 2

本文主要是介绍ARC120D Bracket Score 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

定义一个合法括号序列的权值为 $\sum \mid a_i-a_j\mid$，其中 $(i,j)$ 满足第 $i,j$ 位在括号序列中是配对的。

给定长度为 $2n$ 的序列 $a$，请求出长度为 $2n$ 的权值最大的合法括号序列（不是输出权值，而是输出任意一个解）

---

把 $A$ 从小到大排序后的数组记为 $B$。

考虑如何安排 $n$ 对括号使权值最大。把 $a_i$ 放在数轴上，对于最右边的点，一定是与最左边的点匹配是最优的；对于次右边的点，与次左边的点匹配，以此类推。这是显然的，所以权值不超过 $\sum _{i=n+1}^{2n}{B}_i-\sum _{i=1}^n{B}_i$。下面构造取得最大值。

设 01 数组 $t$，如果 $a_i$ 对应到 $B$ 中的前半部分，$t_i$ 就为 $0$，否则为 $1$。要取到最大值需要使每个匹配 $(i,j)$ 满足 $t_i\oplus t_j=1$。我们一开始先在 $t$ 中找不一样的相邻两个元素，这是一个合法匹配，然后删去这两个，这样不停操作下去，一定可以构造出答案。在实现上，开一个栈，每次对比栈顶和当前 $t_i$，如果不一样，就标记为匹配，否则就放进去栈内。时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+1;
int n,a[N],t[N];
char ans[N];
stack<int> s;
struct node
{int x,i;bool operator<(const node &a)const{return x<a.x;}
}b[N];
int main()
{cin.tie(0)->sync_with_stdio(0);cin>>n;for(int i=1;i<=2*n;i++) cin>>a[i],b[i]={a[i],i};sort(b+1,b+1+n*2);for(int i=1;i<=n;i++) t[b[i].i]=0,t[b[i+n].i]=1;for(int i=1;i<=2*n;i++){if(!s.size()) s.push(i);else{if(t[s.top()]^t[i]){ans[s.top()]='(';ans[i]=')';s.pop();}else s.push(i);}}cout<<(ans+1);
}

这篇关于ARC120D Bracket Score 2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---