出题人题解 | #小A与任务#

原题解链接：https://ac.nowcoder.com/discuss/154293

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

复杂度 $O(nlogn)O(nlogn)$

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
priority_queue<pii> q;
const int N = 2e5 + 5;
struct Node {
  int x, y, z;
  bool operator < (const Node &b) const {
    return y < b.y;
  }
  void input() {
    cin >> z >> x >> y;
  }
} a[N];
int main() {
  int n; cin >> n;
  for (int i = 1; i <= n; i++) a[i].input();
  double ans = 0; int cur = 0;
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; i++) {
    cur += a[i].x;
    q.push(make_pair(a[i].z, a[i].x));
    while (cur > a[i].y) {
      int t = cur - a[i].y;
      pii c = q.top(); q.pop();
      t = min(c.second, t);
      cur -= t;
      ans += 1.0 * t / c.first;
      c.second -= t;
      if (c.second > 0) q.push(c);
    }
  }
  printf("%.1f\n", ans);
  return 0;
}