codeforces-Ed72-B

codeforces-Ed72-B

七月 11, 2020

B. Zmei Gorynich

题意

要杀死生命值为x的龙

有n个武器

每种造成伤害为di 同时龙会恢复hi生命

问最少使用几次杀死怪物

题解

当出现有一种武器能直接杀死龙时输出1

当所有武器都不能杀死龙时输出-1

否则反复使用最大的di-hi武器

最后一次用最大的di攻击能保证次数最少///即龙的血量小于等于斩杀线max di

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# include<bits/stdc++.h>

using namespace std;

# define ms(x, n) memset(x,n,sizeof(x));

typedef  long long LL;
const int inf = 1 << 30;
const int maxn = 110;

int main() {
    LL T, x, n, d, h;
    cin >> T;
    while(T--){
        LL ans = 1, maxD = 0, maxDif = 0;
        cin >> n >> x;
        for(int i = 1; i <= n; ++i){
            cin >> d >> h;
            maxD = max(d, maxD);
            if(d - h > 0)
                maxDif = max(d-h, maxDif);
        }
        if(maxD >= x)
            ans = 1;
        else if(!maxDif)
            ans = -1;
        else if(maxD < x)
            ans += (LL)ceil((double)(x-maxD)/maxDif);
        cout << ans << endl;
    }

return 0;

}
/*
1
2 100
100 101
1 101
*/