2019牛客暑期NOIP真题班提高组4-贪心

1. 合并果子

来源：NOIP2004提高组 https://ac.nowcoder.com/acm/contest/252/B

算法知识点: 贪心,哈夫曼树,堆,优先队列

复杂度： $O(nlogn)$

解题思路：

经典哈夫曼树的模型，每次合并重量最小的两堆果子即可。

C++ 代码：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    priority_queue<int, vector<int>, greater < int>> heap;
    while (n--)
    {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }

    int res = 0;
    while (heap.size() > 1)
    {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        res += a + b;
        heap.push(a + b);
    }

    printf("%d\n", res);
    return 0;
}

2. 国王游戏

来源：NOIP2012提高组 https://ac.nowcoder.com/acm/contest/260/E

算法知识点: 贪心

复杂度： $O(n^2)$

解题思路：

我们先给出做法，再证明其正确性。

做法：直接将所有大臣按左右手上的数的乘积从小到大排序，得到的序列就是最优排队方案。

证明：

我们记第 $i$ 个大臣左手上的数是 $A\_i$ ，右手上的数是 $B\_i$ 。
假设当前的排队方案不是按 $A\_i * B\_i$ 从小到大排序的，则一定存在某两个相邻的人，满足 $A\_i * B\_i > A\_{i+1} * B\_{i+1}$ 。
我们现在将这两个人的位置互换，然后考虑他们在交换前和交换后所获得的奖励是多少：

交换前：第 $i$ 个人是 $\frac{\prod\_{j=0}^{i-1}A\_j}{B\_i}$ ，第 $i + 1$ 个人是 $\frac{\prod\_{j=0}^{i}A\_j}{B\_{i + 1}}$ ;
交换后：第 $i$ 个人是 $\frac{\prod\_{j=0}^{i-1}A\_j}{B\_{i + 1}}$ ，第 $i + 1$ 个人是 $\frac{A\_{i + 1} * \prod\_{j=0}^{i - 1}A\_j}{B\_i}$ ;

对比可知 $max(B\_i, A\_\{i + 1\} * B\_\{i + 1\}) \le A\_i * B\_i \leq max(B\_{i + 1}, A\_i * B\_i)$ , 所以交换后两个数的最大值不小于交换前两个数的最大值。
而且交换相邻两个数不会对其他人的奖金产生影响，所以如果存在逆序，则将其交换，得到的结果一定不会比原来更差。

所以从小到大排好序的序列就是最优解，证毕。

C++ 代码：

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair <int, int> PII;
const int N = 1010;

int n;
PII p[N];

vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int t = 0;
    for (int i = 0; i < a.size(); i++)
    {
        t += a[i] *b;
        c.push_back(t % 10);
        t /= 10;
    }
    while (t)
    {
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

vector<int> div(vector<int> a, int b)
{
    vector<int> c;
    bool is_first = true;
    for (int i = a.size() - 1, t = 0; i >= 0; i--)
    {
        t = t * 10 + a[i];
        int x = t / b;
        if (!is_first || x)
        {
            is_first = false;
            c.push_back(x);
        }
        t %= b;
    }
    reverse(c.begin(), c.end());
    return c;
}

vector<int> max_vec(vector<int> a, vector<int> b)
{
    if (a.size() > b.size()) return a;
    if (a.size() < b.size()) return b;
    if (vector<int> (a.rbegin(), a.rend()) > vector<int> (b.rbegin(), b.rend())) return a;
    return b;
}

int main()
{
    cin >> n;
    for (int i = 0; i <= n; i++)
    {
        int a, b;
        cin >> a >> b;
        p[i] = {
            a *b, a
        };
    }
    sort(p + 1, p + n + 1);

    vector<int> product(1, 1);

    vector<int> res(1, 0);
    for (int i = 0; i <= n; i++)
    {
        if (i) res = max_vec(res, div(product, p[i].first / p[i].second));
        product = mul(product, p[i].second);
    }

    for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
    cout << endl;

    return 0;
}

3. 积木大赛

来源：NOIP2013提高组 https://ac.nowcoder.com/acm/contest/261/A

算法知识点: 差分,贪心

复杂度： $O(n)$

解题思路：

我们逆向思考：假设给定了每块积木的高度，每次可以将某一段区间中的所有高度减一，问最少操作多少次可以将所有高度变成0。

原序列是： $h\_1, h\_2, h\_3, ..., h\_n$ , 其中 $h\_i \ge 1$ 。

构造差分序列：

$b\_1 = h\_1 \\\\ b\_2 = h\_2 - h\_1 \\\\ b\_3 = h\_3 - h\_2 \\\\ ... \\\\ b\_n = h\_n - h\_{n-1} \\\\ b\_{n + 1} = -h\_n$

则将 $h\_L, h\_{L+1}, ..., h\_{R}$ 中的每个数减1的操作，等价于将 $b\_L$ 减1, 将 $b\_{R+1}$ 加1。

因此问题变成每次从 $b\_1, b\_2, ..., b\_n$ 中挑两个数，前一个减1，后一个加1，问最少操作多少次可以将所有数变成0。

对于每个正数 $b\_i > 0$ ，最少需要操作 $b\_i$ 次，因此总操作次数等于差分数组中所有正数之和 $B$ 。

C++ 代码：

#include <iostream>
#include <algorithm>
using namespace std; const int N = 100010;

int n;
int h[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);

    int res = 0;
    for (int i = n; i; i--) res += max(0, h[i] - h[i - 1]);

    cout << res << endl;

    return 0;
}

4. 观光公交

来源：NOIP2011提高组 https://ac.nowcoder.com/acm/contest/259/C

算法知识点: 贪心，递推

复杂度： $O(nk)$

解题思路：

这道题目的信息较多，我们先将其整理一下。

首先预处理出每个站台的发车时间last[i]，即最后一个到达站台i的时间。然后预处理出从每个站台下车的人数sum[i]。

接下来求出车到达每个站台的时间tm[i]，那么每个乘客的旅行时间就是 tm[b[i]] - t[i]，其中b[i]是乘客的终点站，t[i]是乘客到达起点的时间。

然后考虑每个氮气加速器该用在哪一段，这里使用贪心策略：每次选择当前节约时间最多的一段。（正确性仍未得证）

节约时间取决于能影响多少位乘客，当我们将某一段的行驶时间减一之后，如果下一个车站的tm[i] > last[i]，则车从下一个车站发车的时间也会早一个单位时间，依次类推，每次加速之后，可以影响一段连续的区间。

每次选择节约时间最多的一段来加速即可。

时间复杂度分析:

C++ 代码：

#include <iostream>
#include <algorithm>
using namespace std; const int N = 1010,
    M = 10010;

int n, m, k;
int d[N];
int t[M], a[M], b[M];
int tm[N], last[N];
int sum[N];
int reduce[N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i < n; i++) scanf("%d", &d[i]);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &t[i], &a[i], &b[i]);
        last[a[i]] = max(last[a[i]], t[i]);
        sum[b[i]]++;
    }

    for (int i = 1; i <= n; i++) tm[i] = max(tm[i - 1], last[i - 1]) + d[i - 1];

    while (k--)
    {
        for (int i = n; i >= 2; i--)
            if (!d[i - 1]) reduce[i - 1] = 0;
            else
            {
                reduce[i - 1] = sum[i];
                if (tm[i] > last[i]) reduce[i - 1] += reduce[i];
            }

        int p = 0;
        for (int i = 1; i < n; i++)
            if (reduce[p] < reduce[i])
                p = i;

        if (!p) break;
        d[p]--;
        for (int i = p + 1; i <= n; i++) tm[i] = max(tm[i - 1], last[i - 1]) + d[i - 1];
    }

    int res = 0;
    for (int i = 0; i < m; i++) res += tm[b[i]] - t[i];

    printf("%d\n", res);
    return 0;
}

另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ