昨天去做了浙大的月赛。身为ACM菜鸟中的菜鸟的我，简直是被虐。 一个下午只看了一题。ZOJ3230，想了一下午只能想到M*N算法，还想了N种剪枝。 后来想想真是异想天开了吧。哎，一百万次的循环已经够呛，还想要有10000*100000的循环。 第二天看了一下最大堆的，又想到昨天Nineright所讲的C++中有优先队列的模版。 于是用了一下，对a排了个序，Ac了。 代码如下:   #include <stdio.h>#include <queue>#include <stdlib.h>#include <algorithm>using namespace std; struct s{    int a;    int b;}pr[100005]; int cmp1(struct s a,struct s b){    return a.a < b.a;} int main(){    int n,m,i,j,k,p;    while(scanf("%d%d%d",&n,&m,&p) != EOF)    {        for(i = 0;i < n;i++)            scanf("%d%d",&pr[i].a,&pr[i].b);        sort(pr,pr+n,cmp1);        priority_queue <int> q;        q.push(0);        i = 0;        while(m--)        {            for(;i < n;i++)                if(pr[i].a <= p)                    q.push(pr[i].b);                else                    break;            if(q.empty()) break;            p += q.top();            q.pop();        }        while(!q.empty()) q.pop();        printf("%d\n",p);    }    return 0;}     最后判断队列为空的那一句非常重要。如果没写的话会超内存。 我太强了。超了四次，最终不依不饶地过了。 非常棒。   系统默认是最大堆，如果要实现最小堆，应该如下写：   struct cmp1{       bool operator ()(const int &i,const int &j){            return j>i;     //最小堆只要把i>j;         }}; priority_queue < int, vector < int >, cmp1 > q;   post by: Kiswell

评论