二分答案刷题5

发布时间:2024年01月22日
?题目来源:kotori的设备 - 洛谷

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

解题步骤:

二分查找过程

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

文章来源:https://blog.csdn.net/weixin_56642379/article/details/135702506
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。