2 solutions

  • 0
    @ 2025-6-1 22:43:33

    虎鲸der理解2: 本题理解难点:如果一个时刻有多个手机没电了,怎么办?我觉得这是这题的难点,能明白这一点之后这就是一道普通的实数二分题了。

    例如数据:

    3 10

    5 5

    5 5

    5 5

    答案为:3。按照我代码里的意思是每个手机用了 1s 来充电让他能用到 3s。那么问题就来了,三把手机在 1s 就都没电了,你只给一把充了电,其他的还是没电了,答案不应该是 1 吗?

    不是的!我们的充电并不是一次性充了 b[i]-a[i]*x,而是充了多次,他的充电时间和为这个值!为什么可以这样做呢?

    首先换手机充电的操作是瞬间完成,其次电量变化是连续的。这也就给了我们充一会一把手机,让它能用到我把其他手机充电到能用到相同时刻的电量的可能。这样我们就可以一直按这样做下去,使其使用时间尽量长。因为使用时间可以二分找到,那么我们对于每把手机的充电量也就可以全部一次性算出来,而不用一份一份算啦。

    (这份没答案嘻嘻:)

    • 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;
      } 
      
      • 1

      Information

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