小A与任务 （贪心 优先队列）

题意:
小A手头有 n 份任务，他可以以任意顺序完成这些任务，只有完成当前的任务后，他才能做下一个任务
第 i 个任务需要花费 xi 的时间，同时完成第 i 个任务的时间不能晚于 yi，时间掌控者向小A提出了一个条件：如果完成第 i 个任务的时间本应是 t ，但小A支付 m 个金币的话，他可以帮助小A在 t − m × z 时刻完成第 i 个任务， zi​ 是时间参数，会在输入中给出
小A想按时完成所有任务，请你帮他制定一个花费金币最少的方案
注意：不能使得某个任务的花费时间小于 0 ,花费的金币可以不是整数：

题解：
贪心
我们首先按照结束时间对这些任务排个序，看看他在截至时间之间做完的话，超出多少时间。

假设在完成第i个任务时，时间超了，那么超出的这段时间我们是需要用金币来完成的，我们设超出的这段时间为t。
那么我们要花费最少的金币，怎么办呢？
因为t是固定的了，根据题目公式

想让m最小，因为t是固定的，那么我们让z尽可能大即可。
那么我们就去找一下已经完成了任务中最大的那个z，他的任务我们用金币来完成，节省下来的时间完成 当前这个工作。
为什么这样呢？因为去完成那个任务的转换比最划算。
就比如说 在相同情况下 A：花1金币可以完成10分钟工作 B：花1金币可以完成1分钟工作。
那么要想让完成时间相同的情况下金币尽量少，我们肯定选择A

怎么快速的找出那个最大的z，那么就用优先队列即可。

再注意一下细节即可。

每次用金币完成的任务时间=超出的这段时间。
已经完成了任务中最大的那个z任务所花费的时间，有可能大于t，也有可能小于t，注意处理即可。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define endl '\n'
#define int long long
const int maxn=2e5+10;

struct node{
    int z,x,y;
}a[maxn];
struct rule{
    bool operator()(const node & a,const node & b){
     return a.y<b.y;
    }
};
struct wazxy{
    int x,y,z;
    wazxy(int a,int b,int c){x=a,y=b,z=c;}
    bool operator<(const wazxy& a)const
    {
        return z<a.z;
    }
};
priority_queue<wazxy> q;

signed main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i].z>>a[i].x>>a[i].y;
    }
    sort(a,a+n,rule());
    int sum=0,pos=0;
    double ans=0;
    for(int i=0;i<n;i++){
        pos+=a[i].x;
        q.push(wazxy(a[i].x,a[i].y,a[i].z));
        if(pos>a[i].y){
            int temp=pos-a[i].y;
            pos=a[i].y;
            while(true){
                wazxy z=q.top();
                q.pop();
                if(temp>z.x){
                    ans+=(double)z.x/(double)z.z;
                    temp-=z.x;
                }
                else{
                    ans+=(double)temp/(double)z.z;
                    q.push(wazxy(z.x-temp,z.y,z.z));
                    temp=0;
                }
                if(temp==0) break;
            }
        }
    }
    printf("%.1f",ans);
    return 0;
}