传送门：牛客练习赛40
题面：
小A手头有 n 份任务，他可以以任意顺序完成这些任务，只有完成当前的任务后，他才能做下一个任务
第 i 个任务需要花费 x_i 的时间，同时完成第 i 个任务的时间不能晚于 y_i ，时间掌控者向小A提出了一个条件：如果完成第 i 个任务的时间本应是 t ，但小A支付 m 个金币的话，他可以帮助小A在 t-m*z_i 时刻完成第 i 个任务， z_i 是时间参数，会在输入中给出
小A想按时完成所有任务，请你帮他制定一个花费金币最少的方案
注意：不能使得某个任务的花费时间小于 0 ,花费的金币可以不是整数
思路：
首先不难想到一个贪心策略：
1.优先完成截止时间靠前的任务。（以y[i]为关键字，从小到大排序，从左到右处理）
2.如果超出截止时间（t > y[i]），花费尽量少的金币缩短时间（ ans += (t-y[i]) / z[i]）
这样的贪心策略是存在问题的。如果靠后的任务不够时间完成，同时这个任务的 z 较小，而前面存在 z 特别大的任务，我们应该支付（更少的）金币去缩短前面的时间。
那么我们对上面的贪心策略做出修改：
1.时间充足的情况下（t+x[i] <= y[i]), 优先完成截止时间靠前的任务.（t += x[i])
2.如果超出截止时间（t > y[i]), 找出前面还能缩短时间 且 z[i] 最大的。
这样一来，正确性上没有问题了，但每次暴力查找能够缩短时间且z[i]最大的，复杂度撑不住。
事实上，我们应该想到，最适合维护这个东西的就是堆(priority_queue)了
代码仅供参考：
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define ____ ios::sync_with_stdio(false);cin.tie(0);
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
const ll INF = (1LL<<60) - 1;
const double eps = 1e-9;
//head
const int maxn = 2e5 + 5;
struct Node{
int k,t,ddl;
bool operator < (const Node & rhs) const {
return ddl < rhs.ddl;
}
} a[maxn];
struct node{
ll k,t;
node(double k,double t):k(k),t(t){};
node(){};
bool operator < (const node & rhs) const {
return k < rhs.k;
}
};
int n;
int main(){
//freopen("data.in","r",stdin);
____
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].k >> a[i].t >> a[i].ddl;
}
sort(a+1, a+n+1);
priority_queue<node> q;
ll t = 0;
double ans = 0;
for(int i = 1; i <= n; i++){
t += a[i].t;
ll t_in_i = a[i].t;
if(t > a[i].ddl){
while((!q.empty()) && a[i].k < q.top().k){
node u = q.top();
q.pop();
if(u.t > t-a[i].ddl){
u.t -= t-a[i].ddl;
ans += double(t-a[i].ddl)/u.k;
t = a[i].ddl;
if(u.t){
q.push(u);
}
break;
}
else{
t -= u.t;
ans += double(u.t)/u.k;
}
}
if(t > a[i].ddl){
ans += double(t - a[i].ddl)/a[i].k;
t_in_i -= t - a[i].ddl;
t = a[i].ddl;
}
}
if(t_in_i){
q.push(node(a[i].k,t_in_i));
}
}
cout << fixed << setprecision(1) << ans << endl;
return 0;
}