首页 > 代码库 > poj 2970 优先队列

poj 2970 优先队列

先按di排序,(从小到大)。然后依次完成合同,若发现第i个合同无法在截止日期前完成,便从之前已经完成的任务中选一个aj最大的合同,付钱来使得这个合同尽快完成。

#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int q;
    int w;
    bool operator < (const node& t) const {
        return q<t.q;
    }
};
struct shsh
{
    int q,w,e;
    bool operator<(const shsh&kk) const{
    return e<kk.e;
    }
}yy[101005];
node k;
priority_queue<node> q;
int main()
{
    int a;
    //priority_queue<node> q;
    while(~scanf("%d",&a))
    {
        while(!q.empty())
            q.pop();
    for(int i=0;i<a;i++)
    {
        scanf("%d%d%d",&yy[i].q,&yy[i].w,&yy[i].e);
    }
    long long ans=0;
    double sum=0;
    sort(yy,yy+a);
    //for(int i=0;i<a;i++)
    //{
        //printf("%d %d %d\n",yy[i].q,yy[i].w,yy[i].e);
    //}
    for(int i=0;i<a;i++)
    {
        ans+=yy[i].w;
        k.q=yy[i].q;
        k.w=yy[i].w;
        q.push(k);
        while(ans>yy[i].e&&!q.empty())
        {
            node ee=q.top();
            q.pop();
            if(ee.w<ans-yy[i].e)
            {
                sum+=ee.w*1.0/ee.q;
                ans-=ee.w;
            }
            else
            {
                ee.w-=ans-yy[i].e;
                sum+=(ans-yy[i].e)*1.0/ee.q;
                ans=yy[i].e;
                q.push(ee);
            }
        }
    }
    printf("%.2f\n",sum);
    }
    return 0;
}//用G++提交,用%.2lf输出会错。。。大哭大哭