题干：

链接：https://ac.nowcoder.com/acm/contest/369/B
来源：牛客网
 

小A手头有 n 份任务，他可以以任意顺序完成这些任务，只有完成当前的任务后，他才能做下一个任务

第 i 个任务需要花费  xixi 的时间，同时完成第 i 个任务的时间不能晚于 yiyi ，时间掌控者向小A提出了一个条件：如果完成第 i 个任务的时间本应是 t ，但小A支付 m 个金币的话，他可以帮助小A在 t−m×zit−m×zi  时刻完成第 i 个任务， zizi 是时间参数，会在输入中给出

小A想按时完成所有任务，请你帮他制定一个花费金币最少的方案

注意：不能使得某个任务的花费时间小于 0 ,花费的金币可以不是整数

输入描述:

第一行一个整数 n ，表示小A的任务数量
接下来n行，每行三个整数，分别表示 zi,xi,yizi,xi,yi

输出描述:

一行一个实数，表示小A最少需要花费的金币数，四舍五入保留一位小数

示例1

输入

复制

5
1 1 2
1 1 3
1 2 4
1 1 4
1 2 5

输出

复制

2.0

说明

在1时刻完成第一个任务,2时刻完成第二个任务,4时刻完成第三个任务,花费1金币在4时刻完成第四个任务,花费1金币在5时刻完成第五个任务

备注:

1≤n≤2×1051≤n≤2×105

1≤xi,zi≤3×1031≤xi,zi≤3×103

1≤yi≤105

解题报告：

贪心。

以完成时间为关键字从小到大排序(可以交换两个完成时间不同的任务来证明这样的正确性)，按这个顺序来做任务，同时维护一个关于 zi 的大根堆，如果规定时间内完不成任务，就从堆里取出 zizi 最大的任务来花费金币，维护每个任务的剩余时间，如果花费金币后剩余时间不为 0 则重新push入堆

复杂度 O(nlogn)

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
typedef pair<ll,ll> PLL;
struct Node {
    ll z,x,y;//第 i 个任务需要花费 xi 的时间，同时完成第 i 个任务的时间不能晚于 yi ,zi是时间参数
} node[MAX];
bool cmp(Node a,Node b) {
    return a.y < b.y;
}
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i<=n; i++) cin>>node[i].z>>node[i].x>>node[i].y;
    sort(node+1,node+n+1,cmp);
    double ans = 0;
    ll cur = 0;
    priority_queue<PLL> pq;
    for(int i = 1; i<=n; i++) {
        pq.push(pm(node[i].z,node[i].x));
        cur += node[i].x;
        while(cur > node[i].y) {
            PLL now = pq.top();pq.pop();
            ll t = min(now.second,cur - node[i].y);
            ans += 1.0*t/now.first;
            cur -= t;
            now.second -= t;
            if(now.second) pq.push(now);
        }
    }
    printf("%.1f\n",ans);
    return 0 ;
 }