解题思路

1. 问题分析：

   • 每个发动机在电压 $( x \leq z_i )$ 时，功率为 $( a_i \times x )$
   • 当电压 $( x > z_i)$ 时，功率为 $( a_i \times z_i + b_i \times (x - z_i) )$
   • 总功率是所有发动机功率之和，且随电压 $( x )$ 单调递增（电压越高，总功率不会减少）

2. 核心思路：

   • 由于总功率随电压单调递增，可使用二分查找寻找最小电压
   • 二分范围：下界为 ( 1 )，上界需足够大（通过理论计算确保覆盖可能的解）
   • 对每个候选电压，计算总功率并与目标 $( p )$ 比较

3. 复杂度分析：

   • 二分查找的范围约为 $( O(10^{12}) )$，需要约 ( 40 ) 次迭代
   • 每次迭代计算总功率需 $( O(n) )$ 时间
   • 总时间复杂度：$( O(n \log p) )$，完全满足约束条件

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

struct Engine {
    ll z, a, b;
};

int main() {
    int n;
    ll p;
    cin >> n >> p;
    
    vector<Engine> engines(n);
    ll sum_a = 0, sum_b = 0, max_z = 0;
    
    for (int i = 0; i < n; ++i) {
        ll z, a, b;
        cin >> z >> a >> b;
        engines[i] = {z, a, b};
        sum_a += a;
        sum_b += b;
        if (z > max_z) {
            max_z = z;
        }
    }
    
    // 计算上界
    ll sum_ab = sum_a + sum_b;
    ll required = (p + sum_ab - 1) / sum_ab;  // 向上取整
    ll high = max(max_z, required);
    ll low = 1;
    ll answer = high;
    
    // 二分查找最小电压
    while (low <= high) {
        ll mid = (low + high) / 2;
        ll total = 0;
        for (const auto& eng : engines) {
            if (mid <= eng.z) {
                total += eng.a * mid;
            } else {
                total += eng.a * eng.z + eng.b * (mid - eng.z);
            }
            if (total >= p) {  // 提前退出，优化性能
                break;
            }
        }
        if (total >= p) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    
    cout << answer << endl;
    return 0;
}

算法标签

• 二分查找
• 单调性应用
• 模拟计算

关键细节

1. 上界计算：

   • 理论最大单位功率为 $( \sum(a_i + b_i) )$（所有发动机都工作在第二模式）
   • 所需电压上限为 $( \max(\text{最大 } z_i, \lceil p / \sum(a_i + b_i) \rceil) )$

2. 二分优化：

   • 计算总功率时，一旦超过 ( p ) 就提前退出循环
   • 整数除法向上取整使用公式 $( (x + y - 1) // y )$

3. 特殊情况处理：

   • 当所有发动机都工作在第一模式即可满足功率需求
   • 当部分或全部发动机需要工作在第二模式才能满足需求

通过二分查找，我们高效地找到了满足总功率要求的最小电压，充分利用了问题的单调性特点。