首页 > 试题广场 >

小A与任务

[编程题]小A与任务

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小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行，每行三个整数，分别表示

输出描述:

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

示例1

输入

输出

2.0

说明

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

备注:

算法知识视频讲解

耕云种月

发表于 2022-01-25 20:46:20

原题解链接：https://ac.nowcoder.com/discuss/154293 以完成时间为关键字从小到大排序(可以交换两个完成时间不同的任务来证明这样的正确性)，按这个顺序来做任务，同时维护一个关于zi z_izi 的大根堆，如果规定时间内完不成任务，就从堆里取出zi z_izi 最展开全文

在刷题的单身狗很开心

发表于 2023-09-24 11:45:52

首先最任务进行排序，首先按截止时间进行排序然后按z的值从大到小进行排序。按截止时间进行排序是因为如果过了截止时间那就相当于没完成，所以比较优先，那之后为什么按照z的值进行排序呢？因为z的值大能耗费更小的钱去买。在做任务的过程中如果前面任务的时间相加超过当前任务的截止时间了，就得需要向前面的任务以及他展开全文

昵称很长很长真是太好了

发表于 2020-12-28 22:06:19

题意:小A手头有 n 份任务，他可以以任意顺序完成这些任务，只有完成当前的任务后，他才能做下一个任务第 i 个任务需要花费 xi 的时间，同时完成第 i 个任务的时间不能晚于 yi，时间掌控者向小A提出了一个条件：如果完成第 i 个任务的时间本应是 t ，但小A支付 m 个金币的话，他可以帮助小A 展开全文

问题信息

思维题

难度：

0条回答 0收藏 14浏览

小A与任务

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

相关试题