题目链接
-
思路:
我们最终需要找到的答案,是每一次上毒药的最小持续时间,使得n次以后,总伤害大于等于h(若毒药还在持续时间内,则刷新时间)。
假设答案是x,则x-1不可行,但是x+1,x+2,···都可行,所以可以考虑二分来做。
由于n很小,所以可以考虑每次找到一个持续时间后(设为mid),遍历n个数,对每一个数判断:
如果a[i] - a[i-1] >= mid, ret += mid
否则ret += a[i] - a[i - 1]
注意:最后一个数需要额外加上一个mid, 因为每次循环,我们完成的只有从a[1]到a[2], a[2]到a[3], ···a[n-1]到a[n], a[n]之后所造成的伤害我们是没有计算的,所以需要加上。
-
代码:
#include <bits/stdc++.h> #define ll long long using namespace std; typedef pair<ll, ll> PII; const int N = 110, mod = 998244353; int n; ll h; ll a[N]; bool check(ll mid) { ll ret = 0; for (int i = 2; i <= n; i ++) { if (a[i] - a[i - 1] > mid) ret += mid; else ret += a[i] - a[i - 1]; } ret += mid; if(ret >= h) return true; else return false; } void solve() { cin >> n >> h; for (int i = 1; i <= n; i ++) cin >> a[i]; ll l = 1, r = h; while(l < r) { ll mid = (l + r) >> 1; if(check(mid)) r = mid; else l = mid + 1; } cout << l << endl; } int main() { ios::sync_with_stdio(0); int T; cin >> T; while(T --) { solve(); } return 0; }