长沙手机网站设计公司,破解软件库合集资料网址大全,十大黑心装修公司,wordpress app中文版【洛谷】P3743 小鸟的设备 的题解
题目传送门
题解
水一道二分 qaq
刚开始考虑的是动态规划#xff0c;但是动态规划并不能维护题目所要求的东西。所以我们将思路转向另一种求最值问题的方法#xff1a;二分答案。
首先#xff0c;如果一个设备在 t t t 的时间内消耗的…【洛谷】P3743 小鸟的设备 的题解
题目传送门
题解
水一道二分 qaq
刚开始考虑的是动态规划但是动态规划并不能维护题目所要求的东西。所以我们将思路转向另一种求最值问题的方法二分答案。
首先如果一个设备在 t t t 的时间内消耗的能量小于或等于原有的能量那么我们自然没有必要浪费时间给它充电因为它在这段时间内的能量不会降为 0 0 0。
然后我们考虑设备消耗的能量大于原有能量的情况。
由于我们并不在乎什么时候给设备充电所以我们只需要对于每一个这样的设备求出我们需要给它充的电即可。求出需要的电的方法显然就是 a i × t − b i a_i \times t - b_i ai×t−bi
然后我们只需要把所有的需要充电的设备需要充的电加起来判断充电宝能否在 t t t 的时间内充这么多的电即可。
若所有设备的消耗能量速度总和还是小于充电器的充电速度输出 − 1 -1 −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;
}
