题解：AT_arc120_d [ARC120D] Bracket Score 2

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

题意

定义一个长度为

2n

的括号序列

s

的价值为：

\sum\limits_{i=1}^n\left|a_{u_i}-a_{v_i}\right|

其中

(u_i,v_i)

表示

s

中一对匹配括号的位置。
最大化价值。

解法

我们拆开绝对值后易得：

a

的前

n

小一定作为负贡献出现，前

n

大一定作为正贡献出现。
那么我们就确定了符号，接下来考虑分配括号。
同样显然地，一对匹配的括号两端一定是异号贡献，依据这个我们直接用 set 维护即可。
复杂度

\mathcal{O}(n\log n)

。
CODE：

CPP

//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)

题解：AT_arc120_d [ARC120D] Bracket Score 2

文章操作

题意

解法

相关推荐

评论

题解：AT_arc120_d [ARC120D] Bracket Score 2