【洛谷】P3743 小鸟的设备 的题解

【洛谷】P3743 小鸟的设备 的题解

题目传送门

题解

水一道二分 qaq

刚开始考虑的是动态规划，但是动态规划并不能维护题目所要求的东西。所以我们将思路转向另一种求最值问题的方法：二分答案。

首先，如果一个设备在 $t$ 的时间内消耗的能量小于或等于原有的能量，那么我们自然没有必要浪费时间给它充电，因为它在这段时间内的能量不会降为 $0$。

然后我们考虑设备消耗的能量大于原有能量的情况。

由于我们并不在乎什么时候给设备充电，所以我们只需要对于每一个这样的设备，求出我们需要给它充的电即可。求出需要的电的方法显然，就是 $a_i\times t-b_i$

然后我们只需要把所有的需要充电的设备需要充的电加起来，判断充电宝能否在 $t$ 的时间内充这么多的电即可。

若所有设备的消耗能量速度总和还是小于充电器的充电速度，输出 $-1$。

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {inline int read() {register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;}inline void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;}
}
using namespace fastIO;
int n;
double p, sum = 0, l = 0, r = 1e10;
double a[100005], b[100005];
int check(double ans) {double q = p * ans;sum = 0;for(int i = 1; i <= n; i ++) {if(a[i] * ans <= b[i]) {continue;}sum += (a[i] * ans - b[i]);}return sum <= q;
}
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);n = read();cin >> p;for(int i = 1; i <= n; i ++) {cin >> a[i] >> b[i];sum += a[i];}if(sum <= p) {write(-1.000000), putchar('\n');return 0;}while(r - l > 1e-6) {double mid = (l + r) / 2;if(check(mid)) {l = mid;}else {r = mid;}}cout << l << endl;return 0;
}