85分求助!!三个re
查看原帖
85分求助!!三个re
845642
jxcm楼主2024/4/5 14:15

分别时2,5,17 RE

#include  <iostream>
using namespace std;
int n;
double p;
double a[200000],b[200000];
double ledge = 0;
/*
右边界计算方法:
    令n=1e5,p=1e5-1,ai都为1e5,bi都为1,计算得最长时间为1e10
*/
double redge = 1e10;
double use_sum = 0;//每秒能量总消耗
bool check(double ans)
{
    double gap_sum = 0;//能量缺口
    //计算gap_sum
    for(int i = 0;i < n;i++)
    {
        //如果初始能量大于这段时间内的消耗的能量,则跳过
        if((b[i] >= a[i]*ans))
        {
            continue;
        }
        //gap_sum为这段时间内的能量缺口
        gap_sum += a[i]*ans - b[i];
    }
    //如果能量缺口大于能提供的能量,返回0
    if(gap_sum > p*ans)
        return 0;
    else
        return 1;
}
int main()
{
    cin >> n >> p;
	for(int i = 0;i < n;i++)
	{
		cin >> a[i] >> b[i];
		use_sum += a[i];
	}
	//如果每秒能量总消耗小于每秒补充,就能无限使用
	if(use_sum <= p)
	{
	    return -1.000000;
	}
	//二分答案
    while(redge - ledge > 1e-6)
    {
		double mid = (redge + ledge) / 2;
		//
		if( check( mid ) )
		{
			ledge = mid;
		}
		else
		{
			redge = mid;
		}
	}
	cout << ledge << endl;
	return 0;
}

2024/4/5 14:15
加载中...