Codeforces772A Voltage Keepsake

原题链接:Codeforces772A

题目大意:有 $n$ 个设备,第 $i$ 个每秒耗电 $a_i$, 初始状态电量 $b_i$。另有一个充电器,每秒给设备能充电 $p$。 不计切换用电设备和切换充电器充电对象的时间,问最多可以连续使用所有的用电设备的最大时间是多少。

二分

二分答案,假设答案为 $x$,则 $[0, x]$ 部分表示该充电器能维持所有设备有电 $x$ 天,浮点数二分出分界线即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;
const double eps = 1e-5, INF = 0X3f3f3f3f3f3f3f3f;

LL n, p;
LL a[N], b[N], sum;

bool check(double x) {
	double tot = 0;
	for (int i = 1; i <= n; i++) {
	    if (x * a[i] > b[i]) tot += x * a[i] - b[i];
	    if (tot > x * p) return false;
	}	
	return true;
}

int main() {
	cin >> n >> p;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		sum += a[i];
	}
	if (p >= sum) puts("-1");
	else {
		double l = 0, r = INF;
		while (r - l > eps) {
			double mid = (l + r) / 2;
			if (check(mid)) l = mid;
			else r = mid;
		}
		cout << l << endl;
	}
    return 0;
}
updatedupdated2020-05-192020-05-19
加载评论
点击刷新