洛谷P3743kotori的设备-创新互联

有 n n n 台设备和可在任何时刻为任意设备每秒充电 p p p 个单位的充电宝。求电量耗尽前使用时间最短的设备的最长使用时间。

对于 100 100 100%的数据 1 ≤ n ≤ 100000 1≤n≤100000 1≤n≤100000， 1 ≤ p ≤ 100000 1≤p≤100000 1≤p≤100000， 1 ≤ a i , b i ≤ 100000 1≤ai,bi≤100000 1≤ai,bi≤100000。

给设备 i i i 充电 k k k 秒( k k k 不一定是整数)其实就是在 b [ i ] b[i] b[i] 的基础上加上 k p kp kp，所以充电的具体时间不会影响答案，我们只需保证：每个设备的原电量 b [ i ] + b[i] + b[i]+ 充电时间 k k k 充电速度 p = p = p= 可用时间* 每个设备的耗电速度 a [ i ] a[i] a[i] (最优)。
如果单位时间内总消耗能量小于单位时间内供应能量，则无解。

#includeusing namespace std;
const int M = 100005;
int n; 
double a[M],b[M],p;
bool check(double x){double sum = 0;
	for(int i = 1;i<= n;i++){if(b[i]< x * a[i]){	sum += x * a[i] - b[i];
		}
	}
	return sum<= p * x;
}
int main(){cin >>n >>p;
	double asum = 0;
	for(int i = 1;i<= n;i++){cin >>a[i] >>b[i];
		asum += a[i];
	}
	if(asum<= p){cout<< -1<< endl;
		return 0;
	}
	double l = 0,r = 1000000;
	while(r - l >0.000001){double mid = (r + l) / 2;
		if(check(mid)){	l = mid;
		}
		else r = mid;
	}
	cout<< l;
	return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧