2186. 猴子拆房

题目描述

题目分析

这一道题有点难度
我们可以想到，我们可以枚举最高楼房。
那么需要的费用就是：所有比它高的楼房的钱数和+比它矮的但又不得不删掉的钱数和。
前面那一个很简单就可以求出来，后面那一个我们可以用堆来做。
首先，我们排一下序。
然后我们建一个堆，先把所有数都加进去。
然后，我们开始从高往低枚举
我们先把当前点前面的点给删掉。
然后，假如高度等于当前枚举的楼房高度的个数为k，那么我们就把可以保存k-1个数全都删掉。
然后我们算一下$sum=所有剩下的数的和$。
如果$sum+所有比它高的楼房的钱数和<ans$，那么我们就更新ans。
然后，我们再把删掉的数给加回来（以后还会用到的）。
这里有一个问题，就是如果sum一个一个算会很耗费时间，所以我们要边做变加减。
就是在插入一个数的时候，我们把sum+x（x为当前所插入的点的权值），反之亦然。

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node
{
    int h,c;
}tr[110000];
int a[110000],b[110000],c[110000],d[110000];
int hz[110000],sum=0,e[110000];int ans=0;
int cmp(const void *xx,const void *yy)
{
    node n1=*(node *)xx;
    node n2=*(node *)yy;
    if(n1.h<n2.h) return 1;
    else return -1;
}
int mymin(int x,int y) {return x<y?x:y;}
void up(int x)
{
    while(a[x]>a[x/2]&&x/2>0)
    {
        int t=a[x];
        a[x]=a[x/2];a[x/2]=t;
        t=d[x];
        d[x]=d[x/2];d[x/2]=t;
        c[d[x]]=x;c[d[x/2]]=x/2;
        x/=2;
    }
}
void down(int x)
{
    while((a[x]<a[x*2]&&x*2<=sum)||(a[x]<a[x*2+1]&&x*2+1<=sum))
    {
        if(x*2==sum||a[x*2]>a[x*2+1])
        {
            int t=a[x];
            a[x]=a[x*2];a[x*2]=t;
            t=d[x];
            d[x]=d[x*2];d[x*2]=t;
            c[d[x]]=x;c[d[x*2]]=x*2;
            x*=2;
        }
        else
        {
            int t=a[x];
            a[x]=a[x*2+1];a[x*2+1]=t;
            t=d[x];
            d[x]=d[x*2+1];d[x*2+1]=t;
            c[d[x]]=x;c[d[x*2+1]]=x*2+1;
            x=x*2+1;
        }
    }
}
void insert(int x,int id)
{
    ans+=x;
    sum++;a[sum]=x;
    c[id]=sum;d[sum]=id;
    up(sum);
}
void dec(int x)
{
    ans-=a[x];
    if(a[x]>a[sum])
    {
        a[x]=a[sum];
        d[x]=d[sum];
        c[d[x]]=x;
        sum--;down(x);
    }
    else
    {
        a[x]=a[sum];
        d[x]=d[sum];
        c[d[x]]=x;
        sum--;up(x);
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&tr[i].h,&tr[i].c);
    }
    qsort(tr+1,n,sizeof(node),cmp);
    tr[n+1].h=-1;int temp=0;hz[0]=0;
    for(int i=1;i<=n;i++)
    {
        hz[i]=hz[i-1]+tr[i].c;
        insert(tr[i].c,i);
    }
    dec(c[1]);
    int min=999999999;
    for(int i=2;i<=n+1;i++)
    {
        if(tr[i].h!=tr[i-1].h)
        {
            int temp2=mymin(sum,i-temp-2);
            for(int j=1;j<=temp2;j++)
            {
                b[j]=a[1];
                e[j]=d[1];
                dec(1);
            }
            if(ans+hz[temp]<min)
            {
                min=ans+hz[temp];
            }
            for(int j=1;j<=temp2;j++)
            {
                insert(b[j],e[j]);
            }
            temp=i-1;
        }
        dec(c[i]);
    }
    printf("%d\n",min);
    return 0;
}