题解 P4989 【二进制之谜】

· · 题解

堆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);
}