pdd0515_2

Posted on | In |
Words count in article: 800 | Reading time ≈ 3

多多君在多多农场的某块林地上种了N颗树苗（(编号1~N)，其中第i颗树有健康度Hi。多多君计划给树苗们浇水，每次给某棵树苗浇水可以使其健康度上升A点;同时由于水的流动，其他树苗的健康度都会上升B点(其中A大于等于B)。为了每棵树苗都能够顺利成长，多多君希望所有树苗的健康度都大于或等于M。多多君想知道，在达到这个目标的前提下，最少的浇水次数是多少。

输入描述

第一行，4个整数N，M，A和B，分别表示农场中树苗的数量、目标达到的健康度、直接浇水增加的健康度和间接浇水增加的健康度。( 1 <= N,M,A,B<= 1,000,000，A >=B) 接下来N行，每行1个整数Hi，分别表示第i棵树苗初始的健康度Hi。(0<= Hi <= 1,000,000 )

输出描述

共一行，1个整数，表示最少的浇水次数使得所有树苗都能达到目标的健康度。

示例：

1
2
3
4
5
6
7
8
9
输入：
4 10 5 3
2
3
6
8

输出：
2

分析：

难度：容易

1
2
3
4
5
6
7
8
9
10
11
根据题目很容易想到，当健康度最小的满足，所有的才会满足
贪心: 每次给健康度最小的+A, 则其他+B
堆：为了每次O(1)时间获得最小值，需要小根堆
以上做法，首先需要枚举次数O(n), 同时每次需要修改所有的值需要O(n),建立堆O(nlogn),总的时间复杂度O(n^2logn)，一定会超时

优化：
1. 对于浇水的次数，可以采用二分优化，当mid次可以做到，尝试减小次数；mid次做不到，增大次数
2、容易想到，每次给最小的增加a，其他+b，这个做法是最优解，但是，这样做，需要每次遍历所有元素去添加
   转化：
        给最小的+a,其他的+b，相当于最小+(a - b),再把目标值-b

代码

  • C++

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
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int h[N];

int main() {
    int n, m, a, b;
    cin >> n >> m >> a >> b;

    for (int i = 1;i <= n;i ++)
        cin >> h[i];

    auto f = [&](int x) {
        // 建立小根堆
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 1;i <= n;i ++)
            pq.push(h[i]);
        
        int t = m;
        /**
         * 贪心：很容易想到，每次给最小的增加a，其他+b，这个做法是最优解
         但是，这样做，需要每次遍历所有元素去添加
         * 转化：
         给最小的+a,其他的+b，相当于最小+(a - b),再把目标值-b
        */
        for (int i = 0;i < x;i ++) {
            // 获取最小值
            int minval = pq.top();
            pq.pop();

            pq.push(minval + a - b);
            t -= b;
        }

        return pq.top() >= t;
    };

    // 二分枚举增加次数，最少0次，最多1000000次
    int l = 0, r = 1000000;
    while (l < r) {
        int mid = l + r >> 1;
        // mid次可以做到，减小次数
        if (f(mid)) r = mid;
        // mid次做不到，增大次数
        else l = mid + 1;
    }

    cout << l << endl;

    return 0;
}
0%