二分答案刷题5

?题目来源：kotori的设备 - 洛谷

这道题可以用二分答案求解。

解题步骤：

二分查找过程：

• 计算中值 mid = (low + high) / 2，这代表当前假设的设备能够同时运行的时间。
• 对于每个设备，计算在时间 mid 内设备消耗的能量 a[i] * mid，并与设备初始能量 b[i] 进行比较。
• 如果某个设备在时间 mid 内消耗的能量超过了它的初始能量 b[i]，计算需要从充电宝额外获取的能量。
• 计算所有设备需要的总额外能量，与充电宝在时间 mid 内能够提供的总能量 p * mid 进行比较。
• 如果所有设备的总额外能量需求小于或等于充电宝能提供的能量，说明设备可以在 mid 时间内运行，此时 low = mid。
• 如果总额外能量需求大于充电宝能提供的能量，说明设备不能在 mid 时间内运行，此时 high = mid。
• 循环执行，直到 high 和 low 的差小于一个很小的阈值（例如 1e-6），这时我们认为找到了最大时间。

?判断无限运行的情况：

• 在二分查找开始前，先检查是否存在设备的能量消耗为0，如果是，则可以无限运行，直接返回 -1。
• 在二分查找过程中，如果在一个非常大的 mid 值（例如 1e10）下，所有设备的总额外能量需求仍然小于或等于充电宝能提供的能量，说明设备可以无限期运行，返回 -1。

• #include <iostream>
  #include <cmath>  // 用于 fabs 函数
  #define maxn 100010// 定义最大设备数量
  using namespace std;
  
  int n, p, a[maxn], b[maxn];
  
  // 检查函数，用于判断在给定时间t内，所有设备是否能够持续运行不耗尽能量
  bool check(double t) {
      double total_power = 0.0;// 计算总共需要额外的能量
      for (int i = 0; i < n; i++) {
          double power_need = a[i] * t;// 计算第i个设备在时间t内的能量需求
          if (power_need > b[i]) {
              total_power += power_need - b[i];// 如果需求大于初始能量，则累加额外需要的能量
          }
      }
      // 如果总需求的额外能量为负或零，则表示所有设备的初始能量足以支撑时间t
      if (total_power <= 0) return true;
      // 否则，检查充电宝在时间t内提供的总能量是否足够覆盖所有额外需求
      return total_power <= p * t;
  }
  
  int main() {
      cin >> n >> p;
      for (int i = 0; i < n; i++) {
          cin >> a[i] >> b[i];
      }
  
      double low = 0, high = 1e10, mid;
      while (fabs(high - low) > 1e-6) {
          mid = (low + high) / 2;
          if (check(mid)) {
              low = mid;
          }
          else {
              high = mid;
          }
      }
  
      // 检查设备是否可以无限期运行
      if (check(1e10)) {
          cout << "-1" << endl; // 如果可以无限期运行，输出 - 1
      }
      else {
          cout.precision(10);//精确到小数点后10位
          cout << fixed << low << endl; 
      }
  
      return 0;
  }