现在的位置: 首页 > 综合 > 正文

二叉堆例题解题报告代码–poj3253、poj2442、poj2010、poj3481

2017年02月22日 ⁄ 综合 ⁄ 共 5017字 ⁄ 字号 评论关闭
poj3253 类似于哈夫曼树,每次选择所有数中最小的两个,所以这里要建造小根堆,并删除最小的两个数,然后求这两个数的和之后再插入,这里用二叉堆的 make_heap(开始要建堆)、heap(中间要调整)、push_heap(要把和插入,但是对于这里,可以简单的求和,放入堆顶,然后调整一下就ok)、pop_heap(对于选择的数删除)
#include <stdio.h>

#define ll long long
#define MAX 20002

int n;
int a[MAX];

void heap(int m)
{
    int t;
    while(m*2 <= n)
    {
        m *= 2;
        if(m+1 <= n && a[m]>a[m+1]) m ++;
        if(a[m] < a[m/2])
        {
            t = a[m];
            a[m] = a[m/2];
            a[m/2] = t;
        }
        else break;
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++) scanf("%d",&a[i]);
	//建堆
    for(int i = n/2; i > 0; i --) heap(i);

    ll ans = 0,pre;
    while(n > 1)
    {
	         //选择第一个,并且删除
        pre = a[1];
        a[1] = a[n];
        n--;
        heap(1);

		//再选择第一个
        pre += a[1];
		//把和放入堆顶 接着调整
        a[1] = pre;
        heap(1);

        ans += pre;//求答案
    }
    printf("%I64d\n",ans);
    return 0;
}
poj2442 题意:有m个序列,每个序列n个数,我们在每个序列中选一个数,那么就有m个数,对应这m个数有一个和,那么对于所有的数,总共有m^n个选法,要求从小到大输出其中最下的n个选法的和
分析:直接暴力时间复杂度太高,这里用到一点dp,对于m个序列,先求出第k-1项序列的n个数,放于A数组,每个数都是k-1个数的和,那么对于第k个序列,把这个序列的第一个和A数组的每一个相加放到B数组,然后把第k个序列的每一个都和A数组的每一个数相加,然后和B中的最大数相比较,如果小,就互换(因为要n个最小的),具体处理如下(用到滚动数组)操作中只要用到一个heap,和最开始的一个make_heap:
//180K 1922MS
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX 2002

int n,m;
int a[2][MAX]; //滚动数组

void heap(int r[],int m)
{
    int t;
    while(m*2 <= n)
    {
        m *= 2;
        if(m +1 <= n && r[m] < r[m+1]) m ++;
        if(r[m] > r[m/2])
        {
            t = r[m/2];
            r[m/2] = r[m];
            r[m] = t;
        }
        else break;
    }
}

int main()
{
    int T;
    int t,flag;
    scanf("%d",&T);
    while(T --)
    {
        flag = 0;
        scanf("%d%d",&m,&n);
        for(int i = 1; i <= n; i ++) scanf("%d",&a[0][i]);
        for(int i = n/2; i > 0; i --) heap(a[flag],i); //首先我们把第一个序列建堆

        for(int i = 2; i <= m; i ++,flag = 1-flag)
        {
            scanf("%d",&t);
            for(int j = 1; j <= n; j ++) a[1-flag][j] = a[flag][j] + t;//把下一个序列的第一个与上一个序列每一个相加得一个新的序列,也具有堆性质
            for(int j = 1; j < n; j ++)//对于这个序列的剩下 n-1个数 与 A 中每一个相加再与 B 的最大比较
            {
                scanf("%d",&t);
                for(int k = 1; k <= n; k ++)
                {
                    if(a[flag][k] + t < a[1-flag][1])
                    {
                        a[1-flag][1] = a[flag][k] + t;
                        heap(a[1-flag],1);          //这里就用到堆的性质
                    }
                }
            }
        }
        sort(a[flag]+1,a[flag] + n+1); //排序输出
        for(int i = 1; i <= n; i ++)
        {
            printf(i==1 ? "%d":" %d",a[flag][i]);
        }
        printf("\n");
    }
    return 0;
}
poj2010  题意:这里有C头牛,每头牛有一个考试分数,和需要资助的钱,我们选择其中的N头牛资助,并且我们只有F的钱,而且我们有一个要求,就是选择的这N头牛,我们需要他们的分数的中位数 最大
处理:既然要分数的中位数,我们就先按照sorce从小到大排序,由于要N个,那么选择第k个牛,前面就有N/2个之后也有N/2个,那么我们只要枚举第N/2~C-N/2的牛即可,又因为要中位数最大,我们就从右到左一一枚举,如果当前这头牛满足条件,那么这头牛的分数就是答案
那么对于满足要求这个条件,我们分别为1~N/2和C-N/2~C 维护left 和right 两个最大堆,left_sum 和 right_sum分别记录左右堆的 和,由于枚举过程中从右到左,那么对于左边的 left需要预处理,left[1]~left[N/2]为维护的对,left[N/2+1]~left[C-N/2] 其中的每个left[i] 表示 枚举i 这头牛的时候,左边选择的N/2头牛的最小资助金和
对于每个点i,left[i]+right_sum+cow[i].fa <= F,就是我们的满足要求
(具体操作如下)
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAX 100005

int N,C,F;

struct Cow
{
    int s,fa;
    bool operator <(const Cow &c)const
    {
        return s < c.s;
    }
} cow[MAX];
int right[MAX],left[MAX],left_sum,right_sum;

void heap(int a[],int n,int m) //最小堆
{
    int t;
    while(m*2 <= n)
    {
        m *= 2;
        if(m+1 <= n && a[m] < a[m+1]) m ++;
        if(a[m] > a[m/2])
        {
            t = a[m/2];
            a[m/2] = a[m];
            a[m] = t;
        }
        else break;
    }
}

void make_heap(int a[],int n)
{
    for(int i = n/2; i > 0; i --) heap(a,n,i);
}

int main()
{
    while(~scanf("%d%d%d",&N,&C,&F))
    {
        for(int i = 1; i <= C; i ++) scanf("%d%d",&cow[i].s,&cow[i].fa);
		//按分数排序
        sort(cow+1,cow+C+1);

		//先构造左边和右边的 N/2 个数
		// 这里注意i 和 j 表示是左右边的牛, 但是我们对于这N/2个数存放left、right都是从下标为1开始,才能维护堆
		left_sum = right_sum = 0;
        for(int i = 1,j = C-N/2+1; i <= N/2; i ++,j ++)
        {
            left[i] = cow[i].fa; left_sum += left[i];
            right[i] = cow[j].fa; right_sum += right[i];
        }
        make_heap(left,N/2); //先把左边建堆

		//因为一开始我们是从C-N/2 这个位置开始往左边枚举,那么对于这个之前我们要预处理一下
		// left[i] 表示枚举i这头牛时,之前的最小的 N/2 个数之和
        for(int i = N/2+1; i <= C-N/2; i ++)
        {
            left[i] = left_sum; //首先这个left值就是 前面的left_sum
			//如果这头牛比之前建堆的 N/2头牛的最大要小,就更新堆,为下一头牛的left_sum准备
            if(cow[i].fa < left[1])
            {
				//              把最大牛减掉   加上新加入的牛
				left_sum = left_sum - left[1] + cow[i].fa;
                left[1] = cow[i].fa;//更新 调整
                heap(left,N/2,1);
            }
        }

        make_heap(right,N/2);
        int ans = -1;
        for(int i = C-N/2; i > N/2; i --) //开始枚举
        {
            if(right_sum+left[i]+cow[i].fa <= F) { ans=cow[i].s; break;}//这头牛满足
            //如果上面不满足,那么就要往左边移,那么对于当前这头牛就要放到右边的堆当中去
            if(cow[i].fa < right[1])
            {
                right_sum = right_sum-right[1]+cow[i].fa;
                right[1]=cow[i].fa;
                heap(right,N/2,1);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
poj3481 
题意:银行处理系统,每一个顾客有一个标记,还有一个优先级,对于操作1,就是添加一个顾客,操作2,服务优先级高的顾客,操作3 服务优先级低的顾客
分析,分维护一个最大堆,和一个最小堆,处理相对于的服务的时候,比如 操作2,我们在最大堆中删除,并且将次顾客标记处理啦,那么对于后面操作3处理过程中如果也是那个顾客,就可以判断是否标记,标记了就先删除,再处理下一个
//1760K 204MS
#include <stdio.h>
#include <string.h>

#define MAX 1000005

struct node
{
    int k,p;
};

node h[MAX],l[MAX]; //最大最小堆
int n1,n2; //两个堆的人数
bool flag[MAX]; //标记

void push1(int k,int p)/
{
    h[++n1].k = k;
    h[n1].p = p;
    int i = n1;
    while(i>1 && h[i/2].p<p)
    {
        h[i].k = h[i/2].k;
        h[i].p = h[i/2].p;
        i /= 2;
    }
    h[i].k = k;
    h[i].p = p;
}
void push2(int k,int p)
{
    l[++n2].k = k;
    l[n2].p = p;
    int i = n2;
    while(i>1 && l[i/2].p>p)
    {
        l[i].k = l[i/2].k;
        l[i].p = l[i/2].p;
        i /= 2;
    }
    l[i].k = k;
    l[i].p = p;
}

void heap1(int m)
{
    int k,p;
    while(m*2 <= n1)
    {
        m*=2;
        if(m+1<=n1 && h[m].p<h[m+1].p) m++;
        if(h[m].p>h[m/2].p)
        {
            k = h[m].k;
            p = h[m].p;
            h[m].k = h[m/2].k;
            h[m].p = h[m/2].p;
            h[m/2].k = k;
            h[m/2].p = p;
        }
        else break;
    }
}
int get1()
{
    while(n1>0 && flag[h[1].k])
    {
        h[1].k = h[n1].k;
        h[1].p = h[n1--].p;
        heap1(1);
    }
    if(n1 == 0) return 0;
    else
    {
        flag[h[1].k] = 1;
        return h[1].k;
    }
}
void heap2(int m)
{
    int k,p;
    while(m*2 <= n2)
    {
        m*=2;
        if(m+1<=n2 && l[m].p>l[m+1].p) m++;
        if(l[m].p<l[m/2].p)
        {
            k = l[m].k;
            p = l[m].p;
            l[m].k = l[m/2].k;
            l[m].p = l[m/2].p;
            l[m/2].k = k;
            l[m/2].p = p;
        }
        else break;
    }
}
int get2()
{
    while(n2>0 && flag[l[1].k])
    {
        l[1].k = l[n2].k;
        l[1].p = l[n2--].p;
        heap2(1);
    }
    if(n2 == 0) return 0;
    else
    {
        flag[l[1].k] = 1;
        return l[1].k;
    }
}

int main()
{
    memset(flag,false,sizeof(flag));
    int a,k,p;
    n1=n2=0;
    while(~scanf("%d",&a))
    {
        if(!a) continue;
        if(a == 1)
        {
            scanf("%d%d",&k,&p);
            flag[k] = 0;
            push1(k,p);push2(k,p);
        }
        else if(a == 2)
        {
            printf("%d\n",get1());
        }
        else
        {
            printf("%d\n",get2());
        }
    }
    return 0;
}
个人愚昧观点,欢迎指正与讨论

抱歉!评论已关闭.