邢台企业网站建设服务,金山网站建设,微商城网站建设资讯,为什么要做企业官网题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/369/B 来源#xff1a;牛客网
小A手头有 n 份任务#xff0c;他可以以任意顺序完成这些任务#xff0c;只有完成当前的任务后#xff0c;他才能做下一个任务
第 i 个任务需要花费 xixi 的时间…题干
链接https://ac.nowcoder.com/acm/contest/369/B 来源牛客网
小A手头有 n 份任务他可以以任意顺序完成这些任务只有完成当前的任务后他才能做下一个任务
第 i 个任务需要花费 xixi 的时间同时完成第 i 个任务的时间不能晚于 yiyi 时间掌控者向小A提出了一个条件如果完成第 i 个任务的时间本应是 t 但小A支付 m 个金币的话他可以帮助小A在 t−m×zit−m×zi 时刻完成第 i 个任务 zizi 是时间参数会在输入中给出
小A想按时完成所有任务请你帮他制定一个花费金币最少的方案
注意不能使得某个任务的花费时间小于 0 ,花费的金币可以不是整数
输入描述:
第一行一个整数 n 表示小A的任务数量
接下来n行每行三个整数分别表示 zi,xi,yizi,xi,yi
输出描述:
一行一个实数表示小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≤n≤2×1051≤n≤2×105
1≤xi,zi≤3×1031≤xi,zi≤3×103
1≤yi≤105
解题报告
贪心。
以完成时间为关键字从小到大排序(可以交换两个完成时间不同的任务来证明这样的正确性)按这个顺序来做任务同时维护一个关于 zi 的大根堆如果规定时间内完不成任务就从堆里取出 zi 最大的任务来花费金币维护每个任务的剩余时间如果花费金币后剩余时间不为 0 则重新push入堆
其实是连续两次贪心的决策
首先贪心按照y关键字排序来确定完成任务的顺序。
然后如果有任务已经在当前局面下完成不了了那也不一定要让他提前也可以选择让前面已经完成过的任务提前完成。这也就是第二步贪心的决策。这一过程是用优先队列动态维护的。
注意虽然这样看起来好像是同一个任务分开时间完成的(反正代码看起来应该是这样的)因为题目要求一个任务需要连续完成也就是不能这个任务做一半了去开另一个任务但是实际上执行的时候是连续完成的因为这里在优先队列中作差的不是任务而是任务提前完成的时间。也就是假设这个任务需要五分钟完成我们可以让他先提前两分钟完成后面下了一个命令要求他在提前十分钟完成但是没办法了只能再提前三分钟了所以就先能提前多少就提前多少是在不够了再去优先队列中找z第二大的元素去提前完成。
这种操作相当于是用优先队列推迟了操作也是提供了反悔的机会当后面确实需要反悔的时候可以贪心的选择一个最优的决策进行反悔。
复杂度 O(nlogn)
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
typedef pairll,ll PLL;
struct Node {ll z,x,y;//第 i 个任务需要花费 xi 的时间同时完成第 i 个任务的时间不能晚于 yi ,zi是时间参数
} node[MAX];
bool cmp(Node a,Node b) {return a.y b.y;
}
int main()
{int n;cinn;for(int i 1; in; i) cinnode[i].znode[i].xnode[i].y;sort(node1,noden1,cmp);double ans 0;ll cur 0;priority_queuePLL pq;for(int i 1; in; i) {pq.push(pm(node[i].z,node[i].x));cur node[i].x;while(cur node[i].y) {PLL now pq.top();pq.pop();ll t min(now.second,cur - node[i].y);ans 1.0*t/now.first;cur - t;now.second - t;if(now.second) pq.push(now);}}printf(%.1f\n,ans);return 0 ;}
