【洛谷 P3743】kotori的设备 题解(二分答案+循环)

news/2024/6/16 8:07:27 标签: 算法, c++

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)ab104 的时候,你能得到本测试点的满分。

样例 #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 1n100000 1 ≤ p ≤ 100000 1\leq p\leq 100000 1p100000 1 ≤ a i , b i ≤ 100000 1\leq a_i,b_i\leq100000 1ai,bi100000


思路

通过循环读取输入,并计算设备的总耗能速度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)ab104 的时候,就能得到本测试点的满分。


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;
}


http://www.niftyadmin.cn/n/5198848.html

相关文章

常见的面试算法题:阶乘、回文、斐波那契数列

1.阶乘算法 Factorial 例如&#xff1a;给出数字5&#xff0c;对其以下的的每个数字相乘&#xff0c;结果等于120 解&#xff1a;递归 Recursive function factorial(n) {// 如果n为0或1&#xff0c;阶乘是1if (n 0 || n 1) {return 1;}// 否则&#xff0c;返回n乘以n-1的…

Linux本地WBO创作白板部署与远程访问

文章目录 前言1. 部署WBO白板2. 本地访问WBO白板3. Linux 安装cpolar4. 配置WBO公网访问地址5. 公网远程访问WBO白板6. 固定WBO白板公网地址 前言 WBO在线协作白板是一个自由和开源的在线协作白板&#xff0c;允许多个用户同时在一个虚拟的大型白板上画图。该白板对所有线上用…

MacOS - Cpolar 在 Mac 上如何使用?

1、下载并配置环境变量 brew tap probezy/core && brew install cpolar 2、 Token 认证 cpolar authtoken xxx 3、安装服务 sudo cpolar service install 4、启动服务 sudo cpolar service start 5、创建隧道 访问地址&#xff1a;http://127.0.0.1:9200&…

python连接hive报错:TypeError: can‘t concat str to bytes

目录 一、完整报错 二、解决 三、 其他报错 一、完整报错 Traceback (most recent call last): File "D:/Gitlab/my_world/hive2csv.py", line 18, in <module> conn hive.Connection(hosthost, portport, usernameusername, passwordpassword, data…

享元模式学习

背景 享元模式(Flyweight Pattern)&#xff1a;运用共享技术有效地支持大量细粒度对象的复用。系统只使用少量的对象&#xff0c;而这些对象都很相似&#xff0c;状态变化很小&#xff0c;可以实现对象的多次复用。由于享元模式要求能够共享的对象必须是细粒度对象&#xff0c…

JVM对象创建与内存分配

对象的创建 对象创建的主要流程&#xff1a; 类加载推荐博客&#xff1a;JVM类加载机制详解 类加载检查 虚拟机遇到一条new指令时&#xff0c;首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用&#xff0c;并且检查这个符号引用代表的类是否已被加载、解析…

leetcode做题笔记242. 有效的字母异位词

给定两个字符串 s 和 t &#xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。 注意&#xff1a;若 s 和 t 中每个字符出现的次数都相同&#xff0c;则称 s 和 t 互为字母异位词。 示例 1: 输入: s "anagram", t "nagaram" 输出: true示例 2: 输…

vue和uni-app的递归组件排坑

有这样一个数组数据&#xff0c;实际可能有很多级。 tree: [{id: 1,name: 1,children: [{ id: 2, name: 1-1, children: [{id: 7, name: 1-1-1,children: []}]},{ id: 3, name: 1-2 }]},{id: 4,name: 2,children: [{ id: 5, name: 2-1 },{ id: 6, name: 2-2 }]} ]要渲染为下面…