2 solutions
-
0
虎鲸der理解2: 本题理解难点:如果一个时刻有多个手机没电了,怎么办?我觉得这是这题的难点,能明白这一点之后这就是一道普通的实数二分题了。
例如数据:
3 10
5 5
5 5
5 5
答案为:3。按照我代码里的意思是每个手机用了 1s 来充电让他能用到 3s。那么问题就来了,三把手机在 1s 就都没电了,你只给一把充了电,其他的还是没电了,答案不应该是 1 吗?
不是的!我们的充电并不是一次性充了 b[i]-a[i]*x,而是充了多次,他的充电时间和为这个值!为什么可以这样做呢?
首先换手机充电的操作是瞬间完成,其次电量变化是连续的。这也就给了我们充一会一把手机,让它能用到我把其他手机充电到能用到相同时刻的电量的可能。这样我们就可以一直按这样做下去,使其使用时间尽量长。因为使用时间可以二分找到,那么我们对于每把手机的充电量也就可以全部一次性算出来,而不用一份一份算啦。
(这份没答案嘻嘻:)
-
0
虎鲸der过程 (看似很难实际也很难(bushi):
这题用二分。
在验证一个使用时间时,若设备已有的能量大于使用时间需要的能量,忽略该设备。
否则用充电器充电,使设备已有的能量等于使用时间需要的能量,并记录需要的能量。
最后比较需要的能量总和和充电器最多提供的能量。
-1特判:
若所有设备的消耗能量速度总和还是小于充电器的充电速度,输出-1。
#include<bits/stdc++.h> using namespace std; int n; double p; const int M=1e5+2; struct energy{ double x; double y; }; energy a[M]; bool check(double k){ double sum=0; for(int i=1;i<=n;i++){ if(a[i].x*k<=a[i].y) continue; sum+=a[i].x*k-a[i].y; } if(sum>k*p) return 0; return 1; } > int main(){ cin>>n>>p; double t=0; double s=0; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; s+=a[i].x; t=max(t,a[i].y/a[i].x); } if(s<=p){ cout<<"-1"; return 0; } double l=0,r=1e10; while(r-l>1e-6){ double m=(l+r)/2; if(check(m)){ l=m; } else{ r=m; } } printf("%.5f",l); return 0; }
- 1
Information
- ID
- 36
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 5
- Tags
- # Submissions
- 3
- Accepted
- 1
- Uploaded By