2019牛客暑期NOIP真题班普及组8-贪心

1.火星人

来源：NOIP2004普及组 https://ac.nowcoder.com/acm/contest/232/D

算法知识点:贪心，全排列

复杂度： $O(nm)$

解题思路：

这道题目可以直接用next_permutation函数来做。

这里我们考虑一下next_permutation函数的原理，然后手动实现一遍。

对于给定的某个排列，我们想求出比它大的最小的排列。
可以从后往前遍历这个排列，找到第一个可以让排列的字典序变大的位置。

只有当序列单调下降时，它才不存在更大的排列，因此我们要找的位置就是第一次出现 $a\_{k-1} < a\_k$ 的位置。

那么此时将 $a\_{k-1}$ 变成比它大的最小数，然后将剩余部分从小到大排序，得到的排列就是比原排列大的最小排列了。

这里有个小优化：

由于 $a\_{k-1}$ 后面的部分已经从大到小排好序，因此只需将其翻转，就可以得到从小到大排序的结果了，不需要使用 sort函数，时间效率可以降到线性。
C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
int q[N];

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

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    while (m -- )
    {
        int k = n - 1;
        while (q[k - 1] > q[k]) k -- ;
        k -- ;
        int t = k;
        while (t + 1 < n && q[t + 1] > q[k]) t ++ ;
        swap(q[t], q[k]);
        reverse(q + k + 1, q + n);
    }

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

2.纪念品分组

来源：NOIP2007普及组 https://ac.nowcoder.com/acm/contest/235/B

算法知识点:贪心，排序

复杂度： $O(nlogn)$

解题思路：

直觉上讲，分组的时候应该尽可能让每一组的价值之和大一些。

由此得到如下算法：

将所有物品按价值排序；
从大到小枚举每个物品，每次给当前物品找一个价值尽可能大的且总价值没有超过上限的“同伴物品”，将两个物品分在一组；
这样求出的组数就是最小值。

下面给出证明。这里可以使用“调整法”：

假设最优解的分组方式和由上述算法得到的分组方式不同。那么我们考虑从后往前第一个分组不同的数，记为 $a$ ，假设由上述算法得到的“同伴物品”是 $b$ ，那么：
- 如果在最优解中， $a$ 单独一组，那么可以直接将 $b$ 从原组中取出，和 $a$ 放在一起，这样并没有增加组数；
- 如果在最优解中， $a$ 和 $c$ 放在一起，由上述算法可知， $c \le b$ ，那么我们可以将 $b$ 和 $c$ 所在位置交换，交换后两组的价值之和都没有超过上限，且这样也没有增加组数。
- 因此通过上述调整，我们可以在不增加组数的情况下，将最优解的分组方式调整成和上述算法相同，且这样的调整方式可以一直进行下去，直到两个方案相同为止。
因此我们可以在不增加组数的情况下，将最优解的方案调整成上述算法得到的方案，因此上述算法可以得到最优解。

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30010;

int n, m;
int w[N];
bool st[N];

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> w[i];

    sort(w, w + n);

    int res = 0;
    for (int i = 0, j = n - 1; i < n; i ++ )
    {
        if (st[i]) continue;
        while (j >= i && (st[j] || w[i] + w[j] > m)) j -- ;
        st[i] = st[j] = true;
        res ++ ;
    }

    cout << res << endl;
    return 0;
}

3.排座椅

来源：NOIP2008普及组 https://ac.nowcoder.com/acm/contest/236/C

算法知识点:贪心,双关键字排序

复杂度： $O(nlogn)$

解题思路：

这道题目的核心，是需要发现如下性质：

不同行、列之间是完全独立的。即不管将哪行、哪列切开，对其余的行列都是没有任何影响的。

因此可以分别考虑行和列。
对于行来说，问题变成：

去掉哪 $K$ 行，可以使得最后剩下的行间的边数最少。这里去掉边数最多的 $K$ 行一定是最优的。否则可以将选出的行替换成边数最多的 $K$ 行，且结果不会变差。
C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010;

int n, m, L, K, D;
PII row[N], col[N];
int q[N];

int main()
{
    cin >> n >> m >> K >> L >> D;

    for (int i = 1; i <= n; i ++ ) row[i].second = i;
    for (int i = 1; i <= m; i ++ ) col[i].second = i;

    while (D -- )
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (abs(x1 - x2) == 1) row[min(x1, x2)].first ++ ;
        else col[min(y1, y2)].first ++ ;
    }

    sort(row + 1, row + n + 1);
    sort(col + 1, col + m + 1);

    int cnt = 0;
    for (int i = n; i > n - K; i -- ) q[cnt ++ ] = row[i].second;
    sort(q, q + cnt);
    for (int i = 0; i < cnt; i ++ ) printf("%d ", q[i]);
    puts("");

    cnt = 0;
    for (int i = m; i > m - L; i -- ) q[cnt ++ ] = col[i].second;
    sort(q, q + cnt);
    for (int i = 0; i < cnt; i ++ ) printf("%d ", q[i]);
    puts("");

    return 0;
}

4.推销员

来源：NOIP2015普及组 https://ac.nowcoder.com/acm/contest/243/A

算法知识点:贪心，前缀和

复杂度： $O(n)$

解题思路：

这道题目的核心是发现如下性质：

向 $x$ 家住户推销产品的最大花费只有两种情况：推销给 $A\_i$ 最大的 $x$ 家；或者推销给 $A\_{i}$ 最大的 $x-1$ 家，然后最后一家尽可能远。

因此可以先将所有住户按 $A\_i$ 从大到小排序。然后利用前缀和思想预处理出余下三个数组：

f[i]表示前i个 $A\_i$ 的和；
g[i]表示前i个 $S\_i$ 的和；
h[i]表示i~n中 $2S\_i + A\_i$ 的最大值；

那么向 $x$ 家住户推销产品的最大花费就是下面两种情况的最大值：

推销给 $A\_i$ 最大的 $x$ 家：f[i] + 2 * g[i]
推销给 $A\_{i}$ 最大的 $x-1$ 家，然后最后一家尽可能远：f[i - 1] + h[i]

参考文献

推销员, Fizzmy

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
PII w[N];
int f[N];   // 表示前i个a的和
int g[N];   // 表示前i个s的最大值
int h[N];   // 表示i~n中2s + a的最大值

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

    sort(w + 1, w + n + 1);
    reverse(w + 1, w + n + 1);

    for (int i = 1; i <= n; i ++ ) f[i] = f[i - 1] + w[i].first;
    for (int i = 1; i <= n; i ++ ) g[i] = max(g[i - 1], w[i].second);
    for (int i = n; i; i -- ) h[i] = max(h[i + 1], 2 * w[i].second + w[i].first);

    for (int i = 1; i <= n; i ++ ) printf("%d\n", max(f[i] + 2 * g[i], f[i - 1] + h[i]));

    return 0;
}

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