2020 China Collegiate Programming Contest - Mianyang Site D.Defuse the Bombs 二分答案

题目分析

题目大意：给定一个炸弹爆炸的时间序列，每次操作可以选择一个炸弹，使其爆炸时间延长 1 S 1S 1S，在完成该操作后，所有的炸弹的爆炸时间缩短 1 S 1S 1S。当某个炸弹的爆炸事件缩短至 − 1 S -1S −1S时，该炸弹立即爆炸。

思路分析：考虑贪心操作。即每次都选取最小爆炸时间的炸弹，对其爆炸时间进行延长。可以发现对于每个操作次数 n u m num num，对于初始爆炸时间序列 a [ i ] a[i] a[i]统计负差值和。这个负差值和即为对于当前操作次数，如果保证所有炸弹不爆炸所需要的最小操作次数。那么根据这个思路，我们可以直接二分答案，每次 c h e c k check check一下 m i d mid mid即可。

Accepted Code

#include 
#define int long long
using namespace std;

const int N = 1e5 + 10;
int a[N], n;

inline bool check(int val){
    int cnt = 0;
    for(int i = 1; i  n;
    for(int i = 1; i > a[i];
    int l = 1, r = 1e18 - 10, ans = -1;
    while(l > 1;
        if(check(mid)) l = mid + 1, ans = max(ans, mid);
        else r = mid - 1;
    }
    cout