算法标签

• 二分答案

简化题解

核心思路

每个细菌在成熟时间 $a_i + t_i$ 开始分裂，之后每秒数量翻倍。使用二分查找找到最小时间 $T$，使得所有细菌在 $T$ 时刻的总数等于 $m$。

简化代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n; ll m;
    cin >> n >> m;
    
    vector<ll> mature(n);
    for (int i = 0; i < n; i++) cin >> mature[i];
    for (int i = 0; i < n; i++) {
        ll t; cin >> t;
        mature[i] += t;
    }
    
    sort(mature.begin(), mature.end());
    
    ll l = 1, r = 2e9, ans = -1;
    while (l <= r) {
        ll T = (l + r) / 2;
        ll sum = 0;
        
        for (int i = 0; i < n && sum <= m; i++) {
            if (T >= mature[i]) {
                ll exp = T - mature[i];
                if (exp > 60) { sum = m + 1; break; }
                sum += (1LL << (exp + 1));
            }
        }
        
        if (sum < m) l = T + 1;
        else if (sum > m) r = T - 1;
        else { ans = T; r = T - 1; }
    }
    
    cout << ans << endl;
    return 0;
}

算法流程

1. 输入处理：计算每个细菌的成熟时间并排序
2. 二分查找：在 $[1, 2\times10^9]$ 范围内二分时间 $T$
3. 数量计算：对于每个 $T$，计算所有细菌的总数
4. 溢出处理：当指数过大时提前终止计算
5. 结果输出：找到满足条件的最小 $T$，否则输出 $-1$

复杂度

• 时间：$O(n \log n + n \log T)$
• 空间：$O(n)$