Educational Codeforces Round 118 (Rated for Div. 2) C. Poisoned Dagger

题目链接

  • 思路:

我们最终需要找到的答案,是每一次上毒药的最小持续时间,使得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;
}

  

上一篇:大厂算法面试之leetcode精讲9.位运算


下一篇:今年暑假不AC(c语言)