CF edu 118 div2 C

直接二分所选伤害时间

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 105;
typedef long long LL;

LL h;
int T,n;
LL q[N];

void solve()
{
    cin >> n >> h;
    for (int i = 0; i < n; i ++ ) cin >> q[i];

    LL l = 0, r = 1e18;
    LL mid;
    while(l < r)
    {
        mid = (l+r)/2;
        LL sum = 0;
        for (int i = 1; i < n; i ++ )
            sum += min(q[i]-q[i-1],mid);
        sum += mid;
        if(sum >= h) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}

int main()
{
    cin >> T;
    while(T --)
    {
        solve();
    }

    return 0;
}