做网站要学,做网站的主要收入,达州设计公司,php网站api接口写法题目链接 这是一道很棒的二分题。 思路#xff1a; 首先先思考什么情况下是可以无限的使用#xff0c;即输出-1. 我们思考可知#xff0c;如果每一秒内所有设备的用电量总和小于等于充电器每秒可以充的电#xff0c;那么这一群设备就可以无限使用。 接下来分析不是无限使用…题目链接 这是一道很棒的二分题。 思路 首先先思考什么情况下是可以无限的使用即输出-1. 我们思考可知如果每一秒内所有设备的用电量总和小于等于充电器每秒可以充的电那么这一群设备就可以无限使用。 接下来分析不是无限使用的情况 题目要求的是满足某个情况的最大值。 很像二分的类型二分题目往往就是求某一个满足情况的最值这样我们只需要寻找上限和下限并对每一次mid值进行检验是否满足这样的模型时间度一般为O( N*Log( L )) L代表的是总区间的长度而N代表的是完成一次判定需要的时间一般题目可以ON进行暴力判断一个值是否满足情况。 那么接下来我们来分析此题目分析在条件区间内是否单调显然可知的单调的因为随着设备使用的最大时间的变大对充电器每秒可以充的电值的要求也变大。 判定的话我们即要判断该最大使用时间的情况下需要充电器每秒可以充值多少电如果这个充电量小于等于题目给定的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 ix;in;i)
#define repd(i,x,n) for(int ix;in;i)
#define pii pairint,int
#define pll pairlong 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 maxn1000010;
const int inf0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
struct node
{int h;int x;
}a[maxn];
int n,p;
bool check(double mid)
{double need0.0000;double sum0.00000;repd(i,1,n){needmid*a[i].x-a[i].h;if(need0.0000000){sumneed;}else{}}return 1.000000*mid*p-sum0.000000;
}
int main()
{gg(n),gg(p);ll sum0ll;repd(i,1,n){gg(a[i].x);gg(a[i].h);sum(1ll*a[i].x);}if(sump){printf(-1\n);}else{double l0.0000;double r1e10;double mid;double ans;while(r-leps){mid(rl)/2.00000;if(check(mid)){lmid;ansl;}else{rmid-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
