2 solutions

  • 0
    @ 2025-6-1 22:41:13

    虎鲸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;
    } 
    

    Information

    ID
    36
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    # Submissions
    3
    Accepted
    1
    Uploaded By