自动搬运

查看原文

来自洛谷，原作者为

	QuantAsk 烟火里成灰，也去的完美。

搬运于2025-08-24 22:05:56，当前版本为作者最后更新于2019-07-04 21:57:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

堆$n\ log\ n$解法

正题

题目链接:https://www.luogu.org/problemnew/show/P4989

题目大意

一个二进制数两两配对，要求

1. 配对的数不能交叉(用同一个区间但不包含)
2. 0在前1在后

要求配对最多的情况下所有配对的距离之和最远。

解题思路

将0视为左括号，1视为右括号，题目变为括号匹配问题。

我们考虑贪心，先是交叉的问题，我们发现如果两个交叉了，我们让他们反过来配对(配对方的那个)的话答案并不会改变。所有我们不要考虑交叉问题。

那我们开始做，首先不考虑配对最多，我们可以开一个小根堆，存储目前所有已经匹配的右括号还有未左括号的位置。然后我们每次到一个右括号时，取出最小的那个与其匹配并计算多出来的代价。然后从新丢入堆中。

这是距离之和最远，但是配对最多怎么办，那么我们定义权值，小根堆维护权值。对于已经匹配的右括号我们权值就是它的位置；对于没有匹配的左括号，我们让它的权值加上一个$-inf$就可以了。

这样就可以保证优先匹配没有匹配的且权值最大。

时间复杂度$O(n\ log\ n)$

$code$

#include<cstdio>
#include<queue>
#include<iostream>
using namespace std;
struct node{
	int wz,w;
};
bool operator <(const node &a,const node &b)
{return a.w<b.w;}
priority_queue<node> q;
int n,ans,a[1000];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		char c;cin>>c;
		a[i]=c-'0';
	}
	for(int i=1;i<=n;i++)
	{
		if(!a[i]) q.push((node){i,233333333-i});
		else{
			if(q.empty()) continue;
			ans+=i-q.top().wz;q.pop();
			q.push((node){i,-i});
		}
	}
	printf("%d",ans);
}