题意:
给出每个任务的单位钱能买的时间(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;
}
AimerAimerAimer
发布了20 篇原创文章 · 获赞 0 · 访问量 225
私信
关注