首页 > Stressful Training
开通博客写题解
头像 又在摸鱼的大熊猫很勤奋努力
发表于 2020-09-28 17:22:26
CF1132D Stressful Training 题目大意 有台电脑，一共要撑过分钟对于每台电脑，他的初始电量为，每分钟消耗电量为问，至少需要一个功率(每分钟)为多大的充电器才能保证的电量都不为负 分析 按照贪心的思想，对于每一分钟，充电器应该用给那个还能坚持的时间最小的那个这一定是一个必要操作 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 林思艺
发表于 2020-09-28 19:51:03
题意 有台电脑,每台电脑，他的初始电量为，每分钟消耗电量为 你有一个功率为的充电器，每分钟可以使一台电脑电量增加。问，至少为多大才能保证在的时间内任意一台电脑电量都不为负 思路 直接二分充电器的功率。那么接下来就考虑如何这个功率值。 考虑使用优先队列，按照还能使用的时间排序，每次贪心的选取可以撑的时 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 shyyhs
发表于 2020-09-29 13:41:05
挺套路的一个题目.问最小的问题,一般就二分一下,且这个单调性真的显然.然后我们注意k只有2e5,完全可以贪心检测,1min..1min的检测嘛,贪心的策略就是ck时间,把我所坚持时间小的优先充电.貌似就么了..代码如下: #include <bits/stdc++.h> using na 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Dear㉿You
发表于 2020-10-05 14:26:33
Stressful Training 分析 这是个贪心 注意到每次只能给一个人的电脑充电，那么考虑最优的充电的顺序。而这个最优的顺序便是先给最早没电的电脑充电(但是我不会证明诶QwQ)。于是只需要用一个优先队列存储一下每一个人的电脑电量消耗完的时间，二分枚举x判断能否符合题目条件 代码 #inc 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 __故人__
发表于 2020-09-29 16:05:07
分析 比较简单的贪心题。我们考虑到二分一个答案 。那么存在 也是成立的。所以这个是具有单调性的。那么为了让所有的点都是合法的。那么肯定要拿出最近一个将要不合法的节点让他的电量 。那么当第 次充电时发现最近的节点没电的时间在 之前，则是个非法答案。那么我们算法就是如果快速找到第一个将要不合法 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 DeNeRATe
发表于 2020-09-28 21:30:39
分析 看到这种满足要求的最小值第一个想法就一定是二分答案我们只需要明确一点即：一定会优先给最快要没电的人充所以很自然就会想到每个事件贪心维护最快要没电的人使用priority_queue（大佬们也可以手写堆。。。）时间复杂度： 温馨提示 如果队列里边没有元素了，那么就返回true，无需多留 当前点 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 SSuryxin
发表于 2021-05-07 21:38:37
Stressful Training 题目描述： Berland SU holds yet another training contest for its students today. nnn students came, each of them brought his laptop. How 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-09-29 11:34:44
题意：有n台笔记本电脑，它们有一个初始电量ai，和每分钟耗电量bi,有一场训练需要持续k分钟，在每一分钟开始时电量不能为负，你能使用一个多大功率的充电器使其能完成训练，如果没有，则输出-1. 思路：二分枚举答案，如果一个超大的功率都不行，则说明没有，输出-1，判断一个功率是否可行，可以记录在该功率时 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 程序蒟蒻
发表于 2020-09-29 23:27:41
看到就会想到要二分这个x的值，那么接下来就考虑如何check()这个这个x值.考虑使用一个优先队列，按照可以撑的时间排序，每次给可以撑的时间最少的点加上x的电，然后每当有可以超过k的，就直接移出队列，当队列为空时，便为成功，然后继续二分即可. #include<iostream> #in 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-10-01 10:55:15
题目描述 第一行输入共有N个同学，带了N个笔记本，N < 2e5 + 1，需要坚持 K 分钟。第二行给出N个整数，每个整数代表笔记本初始电量，a[i] < 1e12 + 1第三行给出N个整数，每个整数代表笔记本每分钟消好电量，b[i] < 1e7 + 1现在你可以买一个充电器，再每 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”