P76037 持续伤害 — 题解

专题： 二分答案
适用题目： 新生 OJ 本地题包中的 P76037，不要直接用于外站同名题。

解题思路

每次攻击增加的有效伤害是与下次攻击间隔和 k 的较小者，最后一次贡献 k；对 k 二分。

复杂度

每组 $O(n\log h)$。

易错点

重叠持续伤害不能重复计算；攻击时间可能达到 $10^{12}$。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int enough(const long long *a,int n,long long h,long long k){
    long long sum=k;
    for(int i=1;i<n;i++){
        long long gap=a[i]-a[i-1];
        sum+=gap<k?gap:k;
        if(sum>=h)return 1;
    }
    return sum>=h;
}
int main(void) {
    int t;scanf("%d",&t);
    while(t--){int n;long long h;scanf("%d%lld",&n,&h);
        long long *a=malloc(n*sizeof(long long));
        for(int i=0;i<n;i++)scanf("%lld",&a[i]);
        long long l=0,r=h;
        while(l+1<r){long long mid=l+(r-l)/2;
            if(enough(a,n,h,mid))r=mid;else l=mid;
        }
        printf("%lld\n",r);free(a);
    }
    return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--){
        int n;
        ll h;
        cin>>n>>h;
        vector<ll>a(n);
        for(auto &v:a)cin>>v;
        ll l=0,r=h;
        while(l+1<r){
            ll k=l+(r-l)/2;
            ll damage=k;
            for(int j=1;j<n;j++)damage+=min(k,a[j]-a[j-1]);
            if(damage>=h)r=k;
            else l=k;
        }
        cout<<r<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。