NC22604小A与任务之间有什么关联？

本文共计938个文字，预计阅读时间需要4分钟。

题目链接+题目+题目描述+辅助头部有n+本任务，他可以以任意顺序完成这些任务，只有完成当前任务后，他才能做下一个任务+第i个任务需要花费(x_i)的时间，同时完成第i个任务+

题目链接

题目

题目描述

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

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

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

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

输入描述

第一行一个整数 n ，表示小A的任务数量
接下来n行，每行三个整数，分别表示\(z_i,x_i,y_i\)

输出描述

一行一个实数，表示小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\leq n \leq 2\times 10^5\)
\(1\leq x_i,z_i\leq 3\times10^3\)
\(1\leq y_i \leq 10^5\)

题解

知识点：贪心，优先队列。

这是一道后悔贪心变种，这里的限制是截止时间，花费是任务消耗时间，收益是按时完成的任务数，即少花费的金币。如果不考虑金币能够补任务的问题，只要按照截止时间从小到大排序，每次超时再将花费时间多的踢出去，最后即可获得最多按时完成的任务。

但是这里要完成所有任务，那么就不能不做任务了，每次超时要用金币补齐。但注意到不一定要补当前做不完的任务，可以缩短之前 \(z\) 最大的任务，即可补上相同时间，但是花费最少，因为花费金币数为 \(\frac{\Delta t}{z}\) ，\(z\) 越大花费越小。

注意任务完成时间不能小于 \(0\)，因为减到 \(0\) 之后就不能回队列了，要是没减完要换下一个减 。

时间复杂度 \(O(n \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h> using namespace std; struct node { int x, y, z; }a[200007]; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); 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, [&](node a, node b) {return a.y < b.y;}); int sum = 0; double ans = 0; priority_queue <pair<int, int>> pq; for (int i = 0;i < n;i++) { sum += a[i].x; pq.push({ a[i].z,a[i].x }); while (sum > a[i].y) { pair<int, int> task = pq.top(); pq.pop(); int delta = min(sum - a[i].y, task.second); ans += (double)delta / task.first; sum -= delta; task.second -= delta; if (task.second) pq.push(task); } } cout << fixed << setprecision(1) << ans << '\n'; return 0; }