Link: Educational Codeforces Round 72 (Rated for Div. 2)

Zmei Gorynich

Description:
You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads!

Initially Zmei Gorynich has x heads. You can deal n types of blows. If you deal a blow of the i-th type, you decrease the number of Gorynich's heads by min(di,curX), there curX is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows hi new heads. If curX=0 then Gorynich is defeated.

You can deal each blow any number of times, in any order.

For example, if curX=10, d=7, h=10 then the number of heads changes to 13 (you cut 7 heads off, but then Zmei grows 10 new ones), but if curX=10, d=11, h=100 then number of heads changes to 0 and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer t independent queries.

Input
The first line contains one integer t (1≤t≤100) – the number of queries.

The first line of each query contains two integers n and x (1≤n≤100, 1≤x≤1e9) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following n lines of each query contain the descriptions of types of blows you can deal. The i-th line contains two integers di and hi (1≤di,hi≤1e9) — the description of the i-th blow.

Output
For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich.

If Zmei Gorynuch cannot be defeated print −1.

Example
input
3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100
output
2
3
-1
Note
In the first query you can deal the first blow (after that the number of heads changes to 10−6+3=7), and then deal the second blow.

In the second query you just deal the first blow three times, and Zmei is defeated.

In third query you can not defeat Zmei Gorynich. Maybe it's better to convince it to stop fighting?
Problem solving:
这道题其实看懂了就会发现，就是那个蜗牛从井底往上爬的问题。每爬多少就会下滑多少。这道题里面是每减少多少就会增加多少。问你多少次之后可以变成零，并且每次减小的是本身还剩下的值和要减的值中的最小值，所以如果可以减少的话，那么一定会有一次减为零。所以我们需要记录两个最大值，一个是每次净减少的值，另一个是每次减少的值。具体看代码
Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m, x, a, b, maxn, maxm;
    cin >> n;
    while (n--)
    {
        maxn = 0, maxm = 0;
        cin >> m >> x;
        for (int i = 0; i < m; i++)
        {
            cin >> a >> b;
            maxn = max(maxn, a); maxm = max(maxm, (a - b));
        }
        if (maxn >= x)//如果存在一次减少的值，只用这个一次就可以变成0
            puts("1");
        else if (maxm == 0)//如果maxm没有变还是0，说明这个它的初始值就不会减小，直接输出-1
            puts("-1");
        else
            cout << 1 + (x - maxn + maxm - 1) / maxm << endl;//除去最后一次减掉的最多的，然后向上取整
    }
    return 0;
}
赏