T掉的二分答案
查看原帖
T掉的二分答案
114012
chichichichi楼主2020/12/2 11:40

RT,一开始写的二分WA了,看了题解之后改了改,结果T了,一直没找到问题……(甚至都快和题解一模一样了)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#define eps 1e-6
using namespace std;
const int maxn=112345;
int  n;
double p,c[maxn],k[maxn];
long long tot;
bool check(double w)
{
	double res=0;
	for(int i=1;i<=n;i++)
	{
		if(k[i]-w*c[i]>eps)
		continue;
		res+=(w*c[i]-k[i])*1.0/p;
	}
	if(res-w>eps)
	return 1;
	return 0;
}
int main(){
	scanf("%d%lf",&n,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf",c+i,k+i);
		tot+=c[i];
	}
	if(p-tot>=0)
	 {
	 	printf("-1\n");
	 	return 0;
	 }
	double l=0.0,r=99999999999999.99999;
	while(r-l>=eps)
	{
		double mid=(l+r)*1.0/2.0;
		if(check(mid))
		r=mid;
		else
		l=mid;
	}
	printf("%.12f\n",l);
	return 0;
}
2020/12/2 11:40
加载中...