題目鏈接

這是一道很棒的二分題。

思路：

首先先思考什么情況下是可以無限的使用，即輸出-1.

我們思考可知，如果每一秒內所有設備的用電量總和小于等于充電器每秒可以充的電，那么這一群設備就可以無限使用。

接下來分析不是無限使用的情況：

題目要求的是滿足某個情況的最大值。

很像二分的類型，二分題目往往就是求某一個滿足情況的最值，這樣我們只需要尋找上限和下限，并對每一次mid值進行檢驗是否滿足，這樣的模型時間度一般為O(? N*Log( L ))

L代表的是總區間的長度，而N代表的是完成一次判定需要的時間，一般題目可以O（N）進行暴力判斷一個值是否滿足情況。

?

那么接下來我們來分析此題目，分析在條件區間內是否單調，顯然可知的單調的，因為隨著設備使用的最大時間的變大，對充電器每秒可以充的電值的要求也變大。

判定的話，我們即要判斷該最大使用時間的情況下，需要充電器每秒可以充值多少電，如果這個充電量小于等于題目給定的P值，那么就代表數據給的充電器可以滿足這個任務，那么區間就可以選到 Mid-R這個區間進行再次查找。

?

本題目要求精度準確到至少1e-4，我開的eps為1e-6，保險一點，

然后區間我們定為 0~ 1e10

這個區間是需要自己分析的，左區間值0，不用多說，右區間值即最大的值，需要用題目的數據范圍進行分析，初始我認為P的最大值為1e9，那么上限也應該是1e9，但是wa了一次，改成1e10就AC了。

然后我再次分析了一下數據范圍，當極限數據，1e5個設備，每一個耗能為1，自帶1e5的電，充電器的功率為1e5-1 （ 不 -1 的話就可以無限使用了）

這個數據情況下，我們可以知道，答案是大于1e9，小于1e10的，所以我們以1e10做峰值。

帶精度問題的二分的方法有兩種，可以見這篇博客。點我

附上我的AC代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb std::ios::sync_with_stdio(false) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define gg(x) getInt(&x) #define eps 1e-6 using namespace std; typedef long long ll; inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ struct node {int h;int x; }a[maxn]; int n,p; bool check(double mid) {double need=0.0000;double sum=0.00000;repd(i,1,n){need=mid*a[i].x-a[i].h;if(need>0.0000000){sum+=need;}else{}}return 1.000000*mid*p-sum>0.000000; } int main() {gg(n),gg(p);ll sum=0ll;repd(i,1,n){gg(a[i].x);gg(a[i].h);sum+=(1ll*a[i].x);}if(sum<=p){printf("-1\n");}else{double l=0.0000;double r=1e10;double mid;double ans;while(r-l>eps){mid=(r+l)/2.00000;if(check(mid)){l=mid;ans=l;}else{r=mid-eps;}}printf("%.5lf\n", ans);}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} } View Code

?

?

轉載于:https://www.cnblogs.com/qieqiemin/p/10236751.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Voltage Keepsake CodeForces - 801C （思维+二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。