Cloud_Player's Notes
0%

贪心和排序

发表于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

b站视频链接：北京理工大学ACM冬季培训课程
课程刷题地址 2020BIT冬训-贪心
本篇博文为看视频学习时的记录与自己的一些总结

贪心和排序

贪心

啥是贪心

  • 不严格的定义：
  • 诶这题咋做啊
  • 诶这xb搞搞好像很对很有道理啊
  • 诶这题过了（蜜汁表情）

贪心是啥

  • 严格（？）的定义：
  • 在对问题求解时，总是做出在当前看来是最好的选择。
  • 也就是说，
  • 不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解

luoguP1181数列分段 Section I

题目描述
对于给定的一个长度为 $N$ 的正整数数列 $A_i$ ，现要将其分成连续的若干段，并且每段和不超过 $M$ （可以等于 $M$ ），问最少能将其分成多少段使得满足要求。
输入格式
第 $1$ 行包含两个正整数 $N,M$，表示了数列 $A_i$ 的长度与每段和的最大值，第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$ ，如题目所述。
输出格式
一个正整数，输出最少划分的段数。
说明：$N \le 1e5，M \le 1e9$
分析：
  入门题
  对于每一段，不断的加入数直到和超过M
  时间复杂度 $O(n)$

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <vector>
#include <numeric>
using namespace std;
//这个是一开始写的，直接就TLE了
int main() {
    int n, m, num, cnt = 0;
    vector<int> a;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        a.push_back(num);
        if (accumulate(a.begin(), a.end(), 0) > m) {
            a.clear();
            a.push_back(num);
            cnt++;
        }
    }
    printf("%d", cnt + 1);
    return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <vector>
using namespace std;
//这才是AC代码
int main() {
    int n, m, num, sum = 0, cnt = 0;
    vector<int> a;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        a.push_back(num);
        sum += num;
        if (sum > m) {
            a.clear();
            a.push_back(num);
            sum = num;
            cnt++;
        }
    }
    printf("%d", cnt + 1);
    return 0;
}

贪心的注意事项

  • 优点
  • 一般非常好想
  • 分支比较少，复杂度低

  • 缺点
  • 不一定对，要求保证贪心结果无后效性

一般贪心题套路

  • 贪心 + 排序
  • 贪心 + 二分

luoguP1090合并果子

题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。
输入格式
共两行。
第一行是一个整数 $n(1\le n\le 10000)$ ，表示果子的种类数。
第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\le a_i\le 20000)$ 是第 $i$ 种果子的数目。
输出格式
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。
分析：
  普及题
  每次合并最小两堆，用优先队列维护
  Huffman编码

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <queue>

using namespace std;
//这是讲这一讲的学长现场写的
int m, n, i, j, ans;
priority_queue<int, vector<int>, greater<int> >q;
int main() {
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &m);
        q.push(m);
    }
    for (j = 1; j < n; j++) {
        int p1 = q.top(); q.pop();
        int p2 = q.top(); q.pop();
        ans += p1 + p2; q.push(p1 + p2);
    }
    printf("%d\n", ans);
    return 0;
}

附优先队列用法示例（C++ reference）

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
#include <functional>
#include <queue>
#include <vector>
#include <iostream>

template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}

int main() {
    std::priority_queue<int> q;

    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);

    print_queue(q);

    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;

    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);

    print_queue(q2);

    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);

    print_queue(q3);

}
/*
Output:
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
8 9 6 7 4 5 2 3 0 1
*/

luoguP1182数列分段 Section II

题目描述
对于给定的一个长度为 $N$ 的正整数数列 $A_{1\sim N}$ ，现要将其分成 $M（M\leq N）$ 段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段。
将其如下分段：
$[4\ 2][4\ 5][1]$
第 $1$ 段和为 $6$ ，第 $2$ 段和为 $9$ ，第 $3$ 段和为 $1$ ，和最大值为 $9$ 。
将其如下分段：
$[4][2\ 4][5\ 1]$
第 $1$ 段和为 $4$ ，第 $2$ 段和为 $6$ ，第 $3$ 段和为 $6$ ，和最大值为 $6$ 。
并且无论如何分段，最大值不会小于 $6$。
所以可以得到要将数列 $4\ 2\ 4\ 5\ 1$ 要分成 $3$ 段，每段和的最大值最小为 $6$ 。
输入格式
第 $1$ 行包含两个正整数 $N,M$ 。
第 $2$ 行包含 $N$ 个空格隔开的非负整数 $A_i$ ，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
说明： $1\leq N\leq 10^5 ，M\leq N，A_i < 10^8$ ， 答案不超过 $10^9$
分析：
  普及题
  二分M，每次贪心验证是否可行
  时间复杂度 $O(n\log n)$

题解：

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
#include <cstdio>

using namespace std;

int a[100005];
int i, j, m, n, l, r = 0, sum, k, mid;
int main() {
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        r += a[i];                  //r为上界
        if (l < a[i]) l = a[i];     //l为下界
    }
    while (l <= r)                  //二分
    {
        mid = (l + r) / 2;
        k = 1; sum = 0;
        for (i = 1; i <= n; i++)
        {
            if (sum + a[i] > mid) { sum = a[i]; k++; }
            else sum += a[i];
        }
        if (k <= m) { r = mid - 1; }
        else l = mid + 1;
    }
    printf("%d\n", r + 1);
    return 0;
}

这里要注意用二分法的下界为这组数中最大的那个的值
学长 while 语句中写的是 (l < r)
个人觉得应改为 while (l <= r)
两个都能AC，但使用题目描述中的例子会发现用 (l < r) 的会输出 $7$
还有别忘了变量 $r$ 的初始化

排序

sort

1
sort(first_pointer, first_pointer + n, cmp);

在之前的C++STL中已讲到：C++STL：sort

结构体sort

1
2
3
4
5
6
7
8
9
10
11
12
struct student
{
    char name[5];
    int score;
}stu[100];

bool cmp(student p, student q)
{
    return p.score > q.score;
}

sort(stu+1, stu+1+n, cmp);

STL的排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector
sort(v.begin(), v.end(), cmp);

queue stack
不能排序

set
本来就有序

map
不需要排序

priority_queue
push后自然有序

另外

1
nth_element(a+l, a+k, a+r);
  • 使得 a 中 [l, r) 区间的第k小处于第k位，不保证其他位置有序
  • 时间复杂度 $O(n)$

  • 主要用途：过2020蓝桥杯选拔H题