CF505E-Mr. Kitayuta vs. Bamboos

题目:

题目描述:

Mr. Kitayuta’s garden is planted with $ n $ bamboos. (Bamboos are tall, fast-growing tropical plants with hollow stems.) At the moment, the height of the $ i $ -th bamboo is $ h_{i} $ meters, and it grows $ a_{i} $ meters at the end of each day.

Actually, Mr. Kitayuta hates these bamboos. He once attempted to cut them down, but failed because their stems are too hard. Mr. Kitayuta have not given up, however. He has crafted Magical Hammer with his intelligence to drive them into the ground.

He can use Magical Hammer at most $ k $ times during each day, due to his limited Magic Power. Each time he beat a bamboo with Magical Hammer, its height decreases by $ p $ meters. If the height would become negative by this change, it will become $ 0 $ meters instead (it does not disappear). In other words, if a bamboo whose height is $ h $ meters is beaten with Magical Hammer, its new height will be $ max(0,h-p) $ meters. It is possible to beat the same bamboo more than once in a day.

Mr. Kitayuta will fight the bamboos for $ m $ days, starting today. His purpose is to minimize the height of the tallest bamboo after $ m $ days (that is, $ m $ iterations of “Mr. Kitayuta beats the bamboos and then they grow”). Find the lowest possible height of the tallest bamboo after $ m $ days.

输入格式:

The first line of the input contains four space-separated integers $ n $ , $ m $ , $ k $ and $ p $ ( $ 1<=n<=10^{5},1<=m<=5000,1<=k<=10,1<=p<=10^{9} $ ). They represent the number of the bamboos in Mr. Kitayuta’s garden, the duration of Mr. Kitayuta’s fight in days, the maximum number of times that Mr. Kitayuta beat the bamboos during each day, and the power of Magic Hammer, respectively.

The following $ n $ lines describe the properties of the bamboos. The $ i $ -th of them ( $ 1<=i<=n $ ) contains two space-separated integers $ h_{i} $ and $ a_{i} $ ( $ 0<=h_{i}<=10^{9},1<=a_{i}<=10^{9} $ ), denoting the initial height and the growth rate of the $ i $ -th bamboo, respectively.

输出格式:

Print the lowest possible height of the tallest bamboo after $ m $ days.

样例:

样例输入1:

1
2
3
4

3 1 2 5
10 10
10 10
15 2

样例输出1:

1

17

样例输入2:

1
2
3

2 10 10 1000000000
0 10
0 10

样例输出2:

1

10

样例输入3:

1
2
3
4
5
6

5 3 3 10
9 5
9 2
4 7
9 10
3 8

样例输出3:

1

14

思路:

实现:

 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
41
42
43
44
45
46
47
48
49

#include "ybwhead/ios.h"
const int maxn = 2e5 + 10;
int n, m, k, c[maxn];
long long a[maxn], p, h[maxn];
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
int check(long long x)
{
    while (!q.empty())
        q.pop();
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++)
        if (x - a[i] * m < h[i])
            q.push(make_pair(x / a[i], i));
    for (int i = 1; !q.empty() && i <= m; i++)
    {
        for (int j = 1; j <= k && !q.empty(); j++)
        {
            pair<long long, long long> tmp = q.top();
            q.pop();
            if (tmp.first < i)
                return 0;
            ++c[tmp.second];
            if (x + c[tmp.second] * p - a[tmp.second] * m < h[tmp.second])
            {
                q.push(make_pair((x + c[tmp.second] * p) / a[tmp.second], tmp.second));
            }
        }
    }
    return q.empty();
}
int main()
{
    long long l, r = 0;
    yin >> n >> m >> k >> p;
    for (int i = 1; i <= n; i++)
        yin >> h[i] >> a[i], r = max(r, h[i] + a[i] * m);
    l = 0;
    r++;
    while (l < r)
    {
        long long mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    yout << l << endl;
    return 0;
}