题解：CF772A Voltage Keepsake

题目的意思很好理解，在这里不做说明。

二分答案

如果需要使用二分答案，必须要满足单调性。

如果

t

的时间满足题目的条件，那么小于

t

的时间一定满足，这就满足了单调性。

二分范围：因为时间不能是负数所以将左边界设为 $0$ ，右边界设置为很大的值，因为是时间越来越小才能更加满足条件。
判断是否满足条件：二分过程中对 $mid$ 判断是否合法。遍历每个设备，若某一个设备在 $mid$ 时间消耗能量大于初始能量，接下来计算出充电宝需补充的能量并求和，最后对比充电宝提供能量与总补充能量需求。

输出答案

如果

mid

满足条件则记录

mid

在二分后输出，如果答案是很大的值那就说明一直满足，可以无限使用，输出

-1

。

给出代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,p;
int a[N],b[N];
double l,r=1e10;
bool check(double z){//判断z是否合法
	double s=0;
	for(int i=1; i<=n; i++){
		if(a[i]*z>b[i]){
			s+=a[i]*z-b[i];
		}
	}
	return p*z>=s;
}
int main() {
	scanf("%d%d",&n,&p);
	for(int i=1; i<=n; i++){
		scanf("%d%d",&a[i],&b[i]);
	}
	while(r-l>=0.0000001){
		double mid=(l+r)/2;
		if(check(mid)==true){//此时的mid合法
			l=mid;
		}
		else{
			r=mid;
		}
	}
	if(r==1e10){
		printf("-1\n");//可以无限使用
	} else {
		cout << r;
	}
	return 0;
}

题解：CF772A Voltage Keepsake

文章操作

二分答案

输出答案

给出代码

相关推荐

评论

题解：CF772A Voltage Keepsake