POJ 2970 The lazy programmer(优先队列)

题意:
给出每个任务的单位钱能买的时间(a)、所需时间(b)和最后期限(d),问最少需要多少钱完成任务。

思路:
C数组按照最后期限(d)从小到大排序,依次处理。
优先队列按照单位钱所能买的时间(a)从大到小排序。
sum表示当前时间点,如果大于当前任务的时间期限,则从优先队列里取出(a)大的来换取时间,使sum减小。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;
struct node
{
    int a,b,d;
    bool operator<(const node &x) const
    {
        return a<x.a;
    }
}c[100005];
bool cmp(node x,node y)
{
    return x.d<y.d;
}
int n;

int main()
{
    ios::sync_with_stdio(false);
    scanf("%d",&n);
    priority_queue<node> q;
    for(int i=0;i<n;i++)
        scanf("%d%d%d",&c[i].a,&c[i].b,&c[i].d);
    sort(c,c+n,cmp);
    double res=0;
    int sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=c[i].b;
        q.push(c[i]);
        while(sum>c[i].d)
        {
            node t=q.top();
            q.pop();
            if(t.b>sum-c[i].d)
            {
                t.b-=sum-c[i].d;
                res+=(sum-c[i].d)*1.0/t.a;
                sum=c[i].d;
                q.push(t);
            }
            else
            {
                sum-=t.b;
                res+=t.b*1.0/t.a;
            }
        }
    }
    printf("%.2f\n",res);
    return 0;
}
POJ 2970 The lazy programmer(优先队列)POJ 2970 The lazy programmer(优先队列) AimerAimerAimer 发布了20 篇原创文章 · 获赞 0 · 访问量 225 私信 关注
上一篇:CodeForces - 777E


下一篇:Spring boot enable Lazy Initialization of bean