0x17 二叉堆

优先队列太好用了手写啥呀

poj1456 经过贪心专题的洗礼以后这题根本就不叫题啊。。。按时间大到小排每次取最大就好

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

struct node

{

    int v,d;

}a[];

bool cmp(node n1,node n2){return n1.d>n2.d;}

priority_queue<int>q;

int main()

{

    int n,mmax=;

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=;i<=n;i++)

            scanf("%d%d",&a[i].v,&a[i].d), mmax=max(mmax,a[i].d);

        sort(a+,a+n+,cmp);

        int tp=,ans=;

        while(!q.empty())q.pop();

        for(int i=mmax;i>=;i--)

        {

            while(tp<=n&&a[tp].d>=i) q.push(a[tp].v), tp++;

            if(!q.empty()) ans+=q.top(), q.pop();

        }

        printf("%d\n",ans);

    }

    return ;

}

poj1456

poj2442 这题还是很有价值的。一开始想了个貌似很对的做法，就是把每一行排完序和第一个作差，差值压进小根堆里面，堆顶出来以后和之前出去的合并，然后用两个LL的变量记录状态判重，结果后来发现只要m>=3就会有循环，然后就会重复，强行map判定又会多删。最后就是两两合并，因为只有两行所以可以省掉一个n，就能过了。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

int a[],c[][];

struct node

{

    int x,y,d1,d2;bool op;

    friend bool operator>(node n1,node n2)

    {

        return (n1.d1+n1.d2)>(n2.d1+n2.d2);

    }

};priority_queue<node,vector<node>,greater<node> >q;

void ins(int x,int y,int d1,int d2,bool op)

{

    node t;

    t.x=x;t.y=y;t.op=op;

    t.d1=d1;t.d2=d2;q.push(t);

}

void merge(int n)

{

    while(!q.empty())q.pop();

    ins(,,c[][],c[][],false);

    for(int i=;i<=n;i++)

    {

        node t=q.top();q.pop();

        a[i]=t.d1+t.d2;

        if(t.x<n)ins(t.x,t.y+,c[][t.x],c[][t.y+],true);

        if(t.y<n&&t.op==false)ins(t.x+,t.y,c[][t.x+],c[][t.y],false);

    }

    for(int i=;i<=n;i++)c[][i]=a[i];

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int m,n,sum=;

        scanf("%d%d",&m,&n);

        for(int j=;j<=n;j++)scanf("%d",&a[j]);

        sort(a+,a+n+);sum+=a[];

        for(int j=;j<=n;j++)c[][j]=a[j]-a[];

        for(int i=;i<=m;i++)

        {

            for(int j=;j<=n;j++)scanf("%d",&a[j]);

            sort(a+,a+n+);sum+=a[];

            for(int j=;j<=n;j++)c[][j]=a[j]-a[];

            merge(n);

        }

        for(int i=;i<n;i++)printf("%d ",sum+c[][i]);

        printf("%d\n",sum+c[][n]);

    }

    return ;

}

poj2442

bzoj1150: [CTSC2007]数据备份Backup ->环形版 bzoj2151: 种树

合并果子就算了

bzoj4198 这个想一想就可以发现对应一个k叉的哈夫曼树嘛。。深度较小的话就加一个变量表示合并的次数，相同情况合并合并次数较小的就好。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

typedef long long LL;

struct node

{

    LL x;int id,mr;

    friend bool operator>(node n1,node n2)

    {

        if(n1.x==n2.x)return n1.mr>n2.mr;

        return n1.x>n2.x;

    }

};priority_queue<node,vector<node>,greater<node> >q;

void insert(LL x,int id,int mr)

{

    node t;

    t.x=x;t.id=id;t.mr=mr;

    q.push(t);

}

struct edge

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int li,deper;LL sum,c[];

void dfs(int x,int dep)

{

    if(x<=li)

    {

        sum+=((LL)dep)*c[x];

        deper=max(dep,deper);

        return ;

    }

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        dfs(y,dep+);

    }

}

int main()

{

    int n,k;node t,p;

    scanf("%d%d",&n,&k);li=n;

    for(int i=;i<=n;i++)

        scanf("%lld",&c[i]), insert(c[i],i,);

    while((n-)%(k-)!=) insert(,++n,);

    int cc=(n-)/(k-);

    len=;memset(last,,sizeof(last));

    for(int i=;i<=cc;i++)

    {

        t.x=;t.id=++n;t.mr=;

        for(int j=;j<=k;j++)

        {

            p=q.top();q.pop();

            t.x+=p.x;t.mr+=p.mr;

            ins(t.id,p.id);

        }

        q.push(t);

    }

    sum=;deper=;

    dfs(q.top().id,);

    printf("%lld %d\n",sum,deper);

    return ;

}

bzoj4198