【51NOD 1461】稳定桌

题面

有一张桌子，有n个腿。第i根腿的长度是li。
现在要拿掉一些腿，使得桌子稳定，拿掉第i根腿需要di的能量。
稳定的条件是，假如拿掉若干条腿之后，桌子还有k个腿，那么长度最长的腿的数目要超过一半。
比如桌子有5根腿，那么至少要有三根腿是最长的。另外，只有一根腿的桌子是稳定的，两个腿的桌子想要稳定，必需长度是一样的。
你的任务是拿掉若干腿，使得桌子稳定，并且所消耗的能量要最少。

Input
单组测试数据。
第一行有一个整数n (1 ≤ n ≤ 10^5)，表示刚开始桌子腿的数目。
第二行包含n个整数li (1 ≤ li ≤ 10^5)，表示第i个腿的长度。
第三行包含n个整数 di (1 ≤ di ≤ 10^5)，表示拿掉第i个腿所消耗的能量。
Output
输出使得桌子稳定所消耗的最少能量。

分析

放在线段树专题的题，但是因为我钻了牛角尖，我就一直想无论如何用优先队列做出来。事实上，仅维护最大最小的线段树题，大多都可以用两个堆怼出来。

还有两个例子，推销员和失意。都是线段树正解，但是优先队列更好怼的题。如果区间的左端点一直恒定不变，那就更好做了。

我们可以枚举每个高度，然后计算当前高度能保留的最大能量。假设枚举的第x_i个腿的高度为k_i且有m_i个。显然，这个都要保留，还有在高度小于k的数中选m-1个能量最大的保留。

我们可以按照高度从小到大排序，只有枚举过的高度的腿的能量才被扔入堆中，那么模型转换为在区间1~x_i中找能量和最大的m_i-1个数，而困难在于m的数量是在变化的。

对顶堆可以维护区间第k大，定义大根堆和小根堆，且保证小根堆的元素都大于大根堆的元素。用这个思想，我们把小根堆的数量稳定在m_i-1，其中所有元素和就是能量和最大的m_i-1个数的能量和。而其他的元素暂时存在大根堆。

每次跳到下一个枚举的腿长的时候，只需要维护小根堆的数量为m_i+1-1个，把多余的弹进大根堆，并消除其贡献，不够，就从大根堆堆顶弹入小根堆补齐。

这是我洗头的时候想到的方法，我告诉了01妹子过后她想卡我，但是弹的次数取决于| m_i-m_i+1 |，最大也就是n，那其实和线段树一样也是nlogn

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
int n,l,r,now;
ll sum,tmp,tot,ans;
struct email
{
    int h;
    ll c;
}a[N];
priority_queue<ll>q1;
priority_queue<ll,vector<ll>,greater<ll> >q2;
bool cmp(email a,email b){return a.h<b.h;}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i].h);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i].c),sum+=a[i].c;
    sort(a+1,a+1+n,cmp);l=r=1;
    while(l<=n)
    {
        now=a[l].h;tmp=0;
        while(a[r].h==now)tmp+=a[r].c,r++;
        while(q2.size()<r-l-1&&!q1.empty())tot+=q1.top(),q2.push(q1.top()),q1.pop();
        while(q2.size()>r-l-1&&!q2.empty())tot-=q2.top(),q1.push(q2.top()),q2.pop();
        ans=max(ans,tot+tmp);
        while(l<r){if(q1.empty()||a[l].c>q1.top())q2.push(a[l].c),tot+=a[l].c;else q1.push(a[l].c);l++;}
    }
    printf("%lld
",sum-ans);
    return 0;
}