创建公司网站 优帮云,网站美化怎么做,中国最顶尖的广告设计公司,培训网站建设情况kotori的设备
题目背景
kotori 有 n n n 个可同时使用的设备。
题目描述
第 i i i 个设备每秒消耗 a i a_i ai 个单位能量。能量的使用是连续的#xff0c;也就是说能量不是某时刻突然消耗的#xff0c;而是匀速消耗。也就是说#xff0c;对于任意实数#xff0c;…kotori的设备
题目背景
kotori 有 n n n 个可同时使用的设备。
题目描述
第 i i i 个设备每秒消耗 a i a_i ai 个单位能量。能量的使用是连续的也就是说能量不是某时刻突然消耗的而是匀速消耗。也就是说对于任意实数在 k k k 秒内消耗的能量均为 k × a i k\times a_i k×ai 单位。在开始的时候第 i i i 个设备里存储着 b i b_i bi 个单位能量。
同时 kotori 又有一个可以给任意一个设备充电的充电宝每秒可以给接通的设备充能 p p p 个单位充能也是连续的不再赘述。你可以在任意时间给任意一个设备充能从一个设备切换到另一个设备的时间忽略不计。
kotori 想把这些设备一起使用直到其中有设备能量降为 0 0 0。所以 kotori 想知道在充电器的作用下她最多能将这些设备一起使用多久。
输入格式
第一行给出两个整数 n , p n,p n,p。
接下来 n n n 行每行表示一个设备给出两个整数分别是这个设备的 a i a_i ai 和 b i b_i bi。
输出格式
如果 kotori 可以无限使用这些设备输出 − 1 -1 −1。
否则输出 kotori 在其中一个设备能量降为 0 0 0 之前最多能使用多久。
设你的答案为 a a a标准答案为 b b b只有当 a , b a,b a,b 满足 ∣ a − b ∣ max ( 1 , b ) ≤ 1 0 − 4 \dfrac{|a-b|}{\max(1,b)} \leq 10^{-4} max(1,b)∣a−b∣≤10−4 的时候你能得到本测试点的满分。
样例 #1
样例输入 #1
2 1
2 2
2 1000样例输出 #1
2.0000000000样例 #2
样例输入 #2
1 100
1 1样例输出 #2
-1样例 #3
样例输入 #3
3 5
4 3
5 2
6 1样例输出 #3
0.5000000000提示
对于 100 % 100\% 100% 的数据 1 ≤ n ≤ 100000 1\leq n\leq 100000 1≤n≤100000 1 ≤ p ≤ 100000 1\leq p\leq 100000 1≤p≤100000 1 ≤ a i , b i ≤ 100000 1\leq a_i,b_i\leq100000 1≤ai,bi≤100000。 思路
通过循环读取输入并计算设备的总耗能速度sum。如果总耗能速度sum小于等于设备充电速度p则输出-1表示无法满足设备的需求。
通过二分法在区间[0, 1e10]内搜索一个最小的时间l作为其中一个设备能量降为 0 0 0 之前最多能使用的时长。
不妨假设电池是有容量的容量为时间x和电池放电速度p的乘积。通过check函数判断在时间x内电池电量剩余情况。如果电池还有剩余电量那么时间太短需要增加时间如果电池没有剩余电量那么时间太长需要减少时间。
注意精度不用控制太严格否则会超时。只要当 a , b a,b a,b 满足 ∣ a − b ∣ max ( 1 , b ) ≤ 1 0 − 4 \dfrac{|a-b|}{\max(1,b)} \leq 10^{-4} max(1,b)∣a−b∣≤10−4 的时候就能得到本测试点的满分。 AC代码
#include iostream
#define AUTHOR HEX9CF
using namespace std;const int N 1e6 7;// 设备
int n;
// 电池充电速度
double p;
// 每秒耗能存储能量
double a[N], b[N];bool check(double x) {double bat p * x;for (int i 1; i n; i) {if (a[i] * x b[i]) {// 自身电量够用continue;}bat - a[i] * x - b[i];}// cout x bat endl;return bat 0;
}int main() {cin n p;double sum 0;for (int i 1; i n; i) {cin a[i] b[i];sum a[i];}if (sum p) {// 总放电速度不高于充电速度cout -1 endl;return 0;}double l, r;l 0;r 1e10;while (r - l 1e-5) {double mid (l r) / 2;if (check(mid)) {// 时间太长r mid;} else {// 时间太短l mid;}}cout l endl;return 0;
}
