[数据结构与算法]洛谷贪心专题讲解 Java语言

贪心专题讲解

提供一份洛谷网站的贪心题的题单

定义：贪心算法（greedy algorithm [8] ，又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

那么，根据实际刷题经验来看，贪心算法就是根据局部最优解能得到全局最优解。其实通常贪心的难点在于靠自己去根据经验判断，猜测是否可以这样来做。如果自己可以迅速证明自己想的局部贪心策略在全局也会是最优的，那么就可以直接快速做。然而，有的时候自己根据贪心的策略做出来了某个题，但是实际上自己没法用公式或者数学推导证明，也是很有可能的，所以更多的贪心的题通常是根据经验去做。

P1223 排队接水

题目描述

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的等待时间 $T_i$。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

样例 #1

样例输入 #1

10 
56 12 1 99 1000 234 33 55 99 812

样例输出 #1

3 2 7 8 1 4 9 6 10 5
291.90

提示

$n\le 1000,t_i\le 10^6$，不保证 $t_i$ 不重复。

当 $t_i$ 重复时，按照输入顺序即可（sort 是可以的）

解题思路

• 采用贪心算法：根据每个人排队取水的时间长短来，越短的越排在前面
• 数组下标$i$从$0$开始，从在计算第$i$个人的取水时间对后续的人排队的等待时间的影响总和，由于当前第$i$个人取水时间，只会对后续的$n?i$个人造成等待的影响，因此可以用$arr[i][0]?(n?i?1)$得到。

该题贪心策略的证明：

我们假定第$i$个人的取水时间为$t_i$,那么如果存在排队的某个下标顺序为$[0...i,j,k...n]$,使得总的等待的时间$t$。我们可以取任意区间内，比如我们这里取$[i,j,k]$，对应的时间为$[t_i,t_j,t_k]$，其中不满足$t_i\le t_j\le t_k$，那么该区间内所耗费的等待时间总长$t_{sum}=t_i?2+t_j?1$,可以看到$t_{sum}$和$t_i,t_j,t_k$均成正线性关系，且$t_i$的系数最大，那么此时当前仅当$t_i\le t_j\le t_k$，才能使得$t_{sum}$是最小的。

结论：因此只有当越小的排在越前面的时候，才会使得整体等待时间耗费最少，而平均等待耗费时间跟整体等待耗费时间成正比，因此也就能使得平均等待耗费时间最少。证明完毕。

代码附上：

在这里题还要注意两点：

• 两位浮点小数输出格式

  System.out.printf("%.2f%n",res/n);
  

• 用二维数组记录对应的下标，因为题目要求我们输出排队的下标顺序，且是从$1$开始，因此要记得在数组下标对应的加$1$

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine().replaceAll(" ", ""));
        String[] s = br.readLine().split(" ");
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = Integer.parseInt(s[i]);
            arr[i][1] = i;
        }
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];
            } else {
                return o1[1] - o2[1];
            }
        });
        double res = 0;
        for (int i = 0 ; i < n; i++) {
            System.out.print(arr[i][1] + 1 + " ");
            res += arr[i][0] * (n - i - 1);
        }
        System.out.println();
        System.out.printf("%.2f%n",res/n);
        bw.close();
        br.close();
    }

}

时间复杂度$O(nlogn)$,空间复杂度$O(logn)$。

P1803 线段覆盖

题目背景

题目描述

现在各大 oj 上有 $n$ 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 $2$ 个及以上的比赛。

输入格式

第一行是一个整数 $n$ ，接下来 $n$ 行每行是 $2$ 个整数 $a_i,b_i$ ( $a_i<b_i$ )，表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例 #1

样例输入 #1

3
0 2
2 4
1 3

样例输出 #1

2

提示

对于 $20\%$ 的数据， $n\le 10$。

对于 $50\%$ 的数据， $n\le 10^3$。

对于 $70\%$ 的数据， $n\le 10^5$。

对于 $100\%$ 的数据， $1\le n\le 10^6$ ， $0\le a_i<b_i\le 10^6$。

解题思路：这个题相当于求的是不含重复区间的最多区间数量。

• 贪心策略：根据区间的右端点升序排列。用$mi$变量记录上一次参加的比赛的结束时间，当前区间的开始时间比上一次记录的结束时间大的话，就更新$mi$为当前比赛的结束时间，同时记录参加的比赛数目增加$1$。

证明：假定存在如下的比赛排列,$[a_0,b_0],[a_1,b_1],[a_2,b_2],...[a_i,b_i],...,[a_j,b_j],[a_{n?1},...,b_{n?1}]$,其中$a_i,b_i$分别代表一个比赛的开始时间和结束时间。且都是按照结束时间$b_k$升序排列的。那么对于任意区间$[a_i,b_i]$而言，要想计算当前时间段已经能够参与的最多的比赛，就是看$a_i$时间段之前，在$l<p$,一共有多少个可以连续的$b_l,b_p$可以满足$b_l\le a_p$.

import java.io.*;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine().replaceAll(" ", ""));
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
           String[] s = br.readLine().trim().split(" ");
           arr[i][0] = Integer.parseInt(s[0]);
           arr[i][1] = Integer.parseInt(s[1]);
        }
        Arrays.sort(arr, (o1, o2) -> {
            return o1[1] - o2[1];
        });
        int res = 0;
        int idx = 0;
        int mi = 0;
        while (idx < n) {
            if (arr[idx][0] >= mi) {
                res++;
                mi = arr[idx][1];
            }
            idx++;
        }
        bw.write(res + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

}

时间复杂度$O(nlogn)$,空间复杂度$O(logn)$。

P1090 [NOIP2004 提高组] 合并果子

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $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}$ 。

样例

样例输入

3 
1 2 9

样例输出

15

提示

对于 $30\%$ 的数据，保证有 $n\le 1000$：

对于 $50\%$ 的数据，保证有 $n\le 5000$；

对于全部的数据，保证有 $n\le 10000$。

解题思路：

• 该题考察的是根据模拟，每次合并最小的两个体力耗费值，然后同时把合并后的值添加到优先队列里，这样可以免得我们每次重复去计算排序这一部分，然后如果优先队列里还有大于等于2个元素，那么就可以从优先队列里取两个最小的值计算合并，且弹出队列。依次往复，就可以得到最小的体力耗费值。

证明：

假设存在$[a_o,a_1,...a_i,...,a_j,...,a_k,a_n?1]$的体力值，任意取出四个数$a_i,a_j,a_k,a_p$，那么假设这四个数当中最小的两个数是$a_i,a_j$，就一定会满足$a_i+a_j\le a_k+a_p$，合并的耗费的体力值$a_i+a_j$也一定是最小的，然后再与任意新的体力值$a_m$合并，一定会满足$a_i+a_j+a_m\le a_k+a_p+a_m$.因此要想得到总体的最小的体力耗费值，当且仅当每次合并两个的体力值是最小的。

代码如下：

import java.io.*;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine().trim());
        String[] s = br.readLine().trim().split(" ");
        int[] arr = new int[n];
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0 ; i < n ; i++) {
            arr[i] = Integer.parseInt(s[i]);
            q.add(arr[i]);
        }
        int res = 0;
        while (q.size() >= 2) {
            int a = q.poll();
            int b = q.poll();
            res += (a + b);
            q.add(a + b);
        }
        bw.write(res + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

}

p3817 小A的糖果

题目描述

小 A 有 $n$ 个糖果盒，第 $i$ 个盒中有 $a_i$ 颗糖果。

小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 $x$，至少得吃掉几颗糖。

输入格式

输入的第一行是两个用空格隔开的整数，代表糖果盒的个数 $n$ 和给定的参数 $x$。

第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 盒糖的糖果个数 $a_i$。

输出格式

输出一行一个整数，代表最少要吃掉的糖果的数量。

样例 #1

样例输入 #1

3 3
2 2 2

样例输出 #1

1

样例 #2

样例输入 #2

6 1
1 6 1 2 0 4

样例输出 #2

11

样例 #3

样例输入 #3

5 9
3 1 4 1 5

样例输出 #3

0

提示

样例输入输出 1 解释

吃掉第 2 盒中的一个糖果即可。

样例输入输出 2 解释

第 2 盒糖吃掉 $6$ 颗，第 4 盒吃掉 $2$ 颗，第 6 盒吃掉 $3$ 颗。

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\le 20$，$a_i,x\le 100$。
• 对于 $70\%$ 的数据，保证 $n\le 10^3$，$a_i,x\le 10^5$。
• 对于 $100\%$ 的数据，保证 $2\le n\le 10^5$，$0\le a_i,x\le 10^9$。

解题思路：

这个题一开始我想的是既然想得到的是「任意两个相邻的盒子中」糖的数量之和不大于$x$，那么我就直接排序，从最大值一路减过来。如果最大的两个盒子里的糖果数量加起来都不大于$x$了，那么所有的盒子里的糖果肯定会满足条件。

但是，忽略了一点，是相邻的。如果初始给定的顺序比如$i,j,k$,，$a[i]+a[j]\le x$且$a[j]+a[k]\le x$，那么实际上就不需要额外吃糖果了，但是根据我的第一想法可能会出现排序后是$j,i,k$，会有$a[i]+a[k]>x$，那么肯定会需要吃掉$a[i]+a[k]?x$颗糖果才行。因此我的第一贪心想法是不对的。这就是一个明显的反例。所以可以看出来，有时候自己想的贪心不一定是正确的贪心策略，如果不是正确的贪心策略的，通常是会出错的。

正确的解题做法：

• 贪心策略：当$i?1$时，只要当前值$a[i]$与前一项的值$a[i?1]$的和大于$x$，那就需要吃掉$a[i]+a[i?1]?x$的糖果，且当前值更新为$x?a[i?1]$.这样的做法就可以保证是最少要吃掉的糖果数量。

证明：

对于$i?1$而言,如果当前值和前一项的和比$x$大的话，那么当前值和前一项的值就可以一起减去$a[i?1]$颗糖果，这样子就可以让任意相邻的两个数的和$a[i]+a[i?1]\le x$且减去的值恰好为两个只超过$x$的部分，而不需要额外多减去。

附上代码：

• 注意当$i$等于$0$的时候，需要看一下$arr[0]$是否直接超过$x$，如果是的话，那第一个数$arr[0]$就需要减去超过的部分$arr[0]?x$，使得$arr[0]=x$

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s1 = br.readLine().trim().split(" ");
        int n = Integer.parseInt(s1[0]);
        int x = Integer.parseInt(s1[1]);
        String[] s2 = br.readLine().trim().split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(s2[i]);
        }
        long res = 0;
        if (arr[0] > x) {
            res += arr[0] - x;
            arr[0] = x;
        }
        for (int i = 1; i < n; i++) {
            if (arr[i] + arr[i - 1] > x) {
                res += (arr[i] + arr[i - 1] - x);
                arr[i] = x - arr[i - 1];
            }
        }
        bw.write(res + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

时间复杂度$O(n)$,空间复杂度$O(1)$

总结一下

1. 贪心算法适用范围有限，仅仅适用于当前策略在局部最优且可以推广至全局最优时，才可以采取贪心策略。
2. 如果能用贪心算法策略且同时可以用动态规划做的时候，贪心算法在很多时候会能比动态规划的时间复杂度要低或者相等，但是众所周知越是能够最优的往往适用范围就有限。
3. 有的时候贪心的题自己也没法第一时间证明是否是正确的，可以大胆猜想去做，如果失败了，就可以举特例去反推。当然贪心只是一种策略，还会需要结合一些其他的数据结构或者数据处理才能解题，比如「排序」、「优先队列」。
4. 如果对于数组或者给定数据有顺序要求的，就通常不能用排序来做，因为这样会有后序性（我的理解是对后序的数据有影响，而排序通常会扰乱给定数据出现的相对顺序），以及给定的数据范围不能超过$10^5$,因为通常排序的时间复杂度是$O(nlogn)$，超过了$10^5$排序的话就会超时。

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系