贪心算法

贪心算法的基本思想：

  • 求解最优化问题的算法包含一系列步骤
  • 每一步都有一组选择
  • 作出在当前看来最好的选择
  • 希望通过作出局部最优选择来达到全局最优选择
    • 贪心算法不一定总产生最优解
    • 贪心算法是否产生优化解，需要严格证明

贪心算法产生最优解的条件：

  • 最优子结构
  • 贪心选择性

贪心是一种思想，并没有固定的模板。

例题一

题解：题目可简化为n（即N）个数里面选m（即M-N）个数使得这些数之和最小。直接贪心取最小的m个数即可。

  • 排序后取从小到大的m个数即可
  • 优化思路：冒泡排序的话冒泡m次即可（保证前m个数是最小的数即可）

例题二

（暑假共有N天，漫展共有M场，N<1000）

题解：记第i场漫展的开始时间为ai，结束时间为bi，记录为[ai,bi]。

易知，第一场漫展结束的越早，能参加下一场漫展的时间也越早，所以可以贪心选择结束时间最早的漫展

记录当天时间为now(初始为0，因为第一天漫展的ai为1)，对所有漫展根据结束时间bi进行从小到大排序。在ai>now的情况下，参加漫展（bi已经按照从小到大排过序了），并更新now=bi。

（可以考虑使用二维数组）

（只有自己才看得懂的草稿）

例题三

（要把所有手办堆到一起，即有一个手办是不需要动的，其他手办移动到该手办上的位置。不需要计算出最少是多少，只需要求出把手办堆在哪）

题解：考虑到最终是把所有手办放到某一个手办的位置上，所以手办都只会朝着1个位置移动（毕竟不可能左右横跳不然做功不可能最少）。那么对于边界的手办来说，只会朝着中心移动，或者自己就是中心。

考虑将手办移动到与下一个手办合并一起移动，每次只考虑移动边界处的两堆手办，贪心移动较轻的手办。最后移动到只剩一堆时，即可得到最优解。

（只有自己才看得懂的草稿）

例题四

题解：（这题他说是原创。。还没有确定最优解，后续我再来研究研究）

练习题

P1614 爱与愁的心痛

题目：洛谷P1614 爱与愁的心痛

因为它只需要求出连续m个数的最小值是多少，所以我们可以稍微改进一下求连续m个数的方法：

代码如下：

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
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < n; i++) {   // 计算第一个 连续m个数的和
            arrayList.add(scanner.nextInt());   // 接受n个数
        }
        int temp = 0;
        for (int i = 0; i < m; i++) {
            temp = temp + arrayList.get(i);
        }
        int min = temp;
        for (int i = 0; i < n - m; i++) {   // 循环n-m次，因为第一次已经计算并存储到min中了
            temp = temp + arrayList.get(i+m) - arrayList.get(i);
            if (temp < min){
                min = temp;
            }
        }
        System.out.println(min);
    }
}

P1803 凌乱的yyy / 线段覆盖

题目：洛谷P1803 凌乱的yyy / 线段覆盖

这里其实就和上面的例题二相似了。

代码如下：

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
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Interval[] intervals = new Interval[n];
        for (int i = 0; i < n; i++) {
            intervals[i] = new Interval(scanner.nextInt(), scanner.nextInt());
        }
        Arrays.sort(intervals);     // 根据我们制定的规则排序
        int sum = 0;
        int now = 0;
        for (Interval interval : intervals) {
            if (now <= interval.begin){ // 当前天数小于等于开始时间才可以参加（从给出的例子中可以看出是小于等于）
                sum++;
                now = interval.end;
            }
        }
        System.out.println(sum);

    }

private static class Interval implements Comparable<Interval>{
        int begin;
        int end;

    public Interval(int begin, int end) {
        this.begin = begin;
        this.end = end;
    }

    /**
     * 重写排序方法
     * 若要利用sort进行排序就要重写compareto函数
     * @param o
     * @return
     */
    @Override
    public int compareTo(Interval o) {
        return this.end - o.end;
    }
}

}

说明，本来我写的代码是这样的：

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
package luoguCode.P1803.greedy;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] dates = new int[n][2];
        int[] temp = new int[2];
        for (int i = 0; i < n; i++) {   // 接受输入的日期
            dates[i][0] = scanner.nextInt();
            dates[i][1] = scanner.nextInt();
        }
        for (int i = 0; i < dates.length; i++) {
            for (int j = i+1; j < dates.length; j++) {
                if (dates[i][1] > dates[j][1]){ // 根据结束时间从小到大排序
                    temp = dates[i];
                    dates[i] = dates[j];
                    dates[j] = temp;
                }
            }
        }
        int now = 0;    // 当前天数
        int sum = 0;    // 能参加的比赛数目
        for (int i = 0; i < dates.length; i++) {
            if (now <= dates[i][0]){     // 当前天数小于等于开始时间才可以参加（从给出的例子中可以看出是小于等于）
                sum++;
                now = dates[i][1];
            }
        }

        System.out.println(sum);

    }
}

但是会有两个测试集超时了，所以我改进成如上的代码。

Java Collections工具类（Comparable和Comparator）

P1090 合并果子

题目：洛谷P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

这题的贪心思想很简单，就是每次都找到最小的两堆果子，将其合并后放到新的果子队列中，然后再在新的果子队列中找到最小的两堆果子合并，合并后的新果子堆再放到果子队列中……直到果子队列中只剩下一个果子堆。

这题关键在于能不能想到使用优先队列（具体来说是升序优先队列，即总是先删除最小的元素）。使用优先队列这题就会非常好做了。

代码如下：

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        Integer n = new Integer(bufferedReader.readLine());
        // 输入以空格为间隔，所以我们以空格将其拆分为一个String数组
        String[] strings = bufferedReader.readLine().split(" ");
        // 生成优先队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (String string : strings) {
            priorityQueue.add(new Integer(string));
        }
        int temp = 0;
        int sum = 0;
        while (priorityQueue.size()>1){ // 当优先队列长度为1时，停止循环
            Integer a1 = priorityQueue.poll();
            Integer a2 = priorityQueue.poll();
            temp = a1+a2;
            sum = sum+temp;
            priorityQueue.add(temp);
        }
        System.out.println(sum);
    }
}

代码说明：PriorityQueue类和BufferedReader类

说明：Java中的优先队列，可以使用PriorityQueue类。Java 优先级队列 PriorityQueue

这里我在jdk1.8中文版.CHM文件（本地路径：D:\Java_study。其实就是jdk1.8文档啦）中查找到一些常用的方法如下：

  • boolean add(E e) ：将指定的元素插入到该优先队列中
  • void clear() ：从这个优先队列中移除所有的元素
  • Comparator<? super E> comparator() ：返回用于为该队列中的元素的比较，或 null如果这个队列是根据其元素的 natural ordering排序
  • boolean contains(Object o) ：返回 true如果此队列包含指定的元素
  • Iterator<E> iterator() ：返回此队列中元素的迭代器
  • boolean offer(E e) ：将指定的元素插入到该优先队列中
  • E peek() ：检索，但不删除，这个队列头，如果队列为空返回 null
  • E poll() ：检索并移除此队列的头，如果队列为空返回 null
  • boolean remove(Object o) ：从该队列中移除一个指定指定元素，如果它是存在的
  • int size() ：返回此集合中的元素的数目
  • Object[] toArray() ：返回一个包含此队列中所有元素的数组
  • <T> T[] toArray(T[] a) ：返回包含此队列中的所有元素的数组；返回数组的数组类型是指定的数组的类型（即<T> T[]）

add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后则则会返回false。对于PriorityQueue这两个方法其实没什么差别。（深入理解Java PriorityQueue）

还有一点，从这个程序开始，我们就开始使用BufferedReader来接受数据了，这是因为**Scanner的平均耗时是BufferedReader的10倍左右。**初次使用BufferReader可能会不太习惯，用多了就好了。（java Scanner与BufferedReader读取键盘输入性能比较）

BufferedReader常用方法：

  • int read() ：读取单个字符
  • String readLine() ：读一行文本

给两个例子吧：

1
2
3
4
5
6
7
8
9
10
InputStreamReader inputStreamReader = new InputStreamReader(System.in);
BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
Integer n = new Integer(bufferedReader.readLine());
// 输入以空格为间隔，所以我们以空格将其拆分为一个String数组
String[] strings = bufferedReader.readLine().split(" ");
// 生成优先队列
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (String string : strings) {
    priorityQueue.add(new Integer(string));
}
1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) throws IOException {
    InputStreamReader inputStreamReader = new InputStreamReader(System.in);
    BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
    Integer n = new Integer(bufferedReader.readLine());
    int[] arr = new int[n];
    String[] strings = bufferedReader.readLine().split(" ");
    for (int i = 0; i < strings.length; i++) {
        arr[i] = new Integer(strings[i]);
    }
    System.out.println(n);
    System.out.println(Arrays.toString(arr));
}

P1190 接水问题

题目：P1190 [NOIP2010 普及组] 接水问题

分析：这题的思路有点意思。首先从题意很容易想到要用优先队列，但是我一开始想的是先将优先队列中poll一个值，然后在队列中的剩余元素减去poll的这个值，然后再往队列中add一个同学。但是这样显然是不好实现的。所以我们不妨换一个思路：把poll出来的值作为waitTime加在要进入队列的下一个同学中，作为等待时间。在所有同学都进入队列后（即没有排队的同学），队列中会有m个同学（有m个水龙头嘛，很好理解），我们将这m个数据依次poll出来，取最后一个poll的值（即最后一个同学接完水后），即为我们要的接水总时间。

代码如下：

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
package luoguCode.P1190.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        InputStreamReader inputStreamReader = new InputStreamReader(System.in);
        BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
        String[] strings = bufferedReader.readLine().split(" ");
        int n = new Integer(strings[0]);    // 接水人数
        int m = new Integer(strings[1]);     // 龙头个数
        int[] arr = new int[n];
        String[] strings2 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = new Integer(strings2[i]);
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(m);
        for (int i = 0; i < m; i++) {
            priorityQueue.add(arr[i]);
        }
        int waitTime = 0;    // 一个同学完成接水后花费的时间（即下一个同学等待的时间）
        for (int i = m; i < n; i++) {
            waitTime = priorityQueue.poll();
            priorityQueue.add(arr[i]+waitTime);  // 关键的一步，将进入队列的同学的等待时间加上
        }
        int result = 0;
        while (!priorityQueue.isEmpty()){   // 上一个for循环结束后，队列中还有m个元素
            result = priorityQueue.poll();
        }
        System.out.println(result);
    }
}

P7427 玩游戏

题目：P7427 [THUPC2017] 玩游戏

分析：首先，由于分数之和只能是1+2+3+…n的一个整数解，所以我们先判断输入的a和b之和sum，有没有整数解n。若没有整数解，直接输出No；若有整数解，由于题目中只需要一种可能的解，所以我们就不需要用经典的寻找和为定值的多个数问题（背包问题的应用），而是用贪心算法。贪心思想为：每次取1-n中最大的值n，存入到ArrayList中，然后sum-n，然后再判断sum-(n-1)，若为0，直接退出循环，若小于0，继续循环但不讲n-1存入到ArrayList中。（因为已经确定）这一段贪心思想具体体现在：

1
2
3
4
5
6
7
8
9
10
11
12
long sum = a;
ArrayList<Long> arrayList = new ArrayList<>();
for (long l = n; l > 0; l--) {
    if (sum-l<0){
        continue;
    }
    if (sum==0){
        break;
    }
    arrayList.add(l);
    sum = sum - l;
}

代码如下：

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = bufferedReader.readLine().split(" ");
        long a = new Long(strings[0]);    // 接受a的值
        long b = new Long(strings[1]);    // 接受b的值
        long n = func(a + b);
        if (n==-1||a==0&&b==0){
            System.out.println("No");
        }else {// 这一段代码是关键部分（即在连续的1,2,3...n这n个数中找到若干个数相加为a）
            // 即经典的寻找和为定值的多个数问题（背包问题的应用）
            // 但是由于题目只需要一种可能的解，我们可以用贪心思想来实现输出一种可能的解
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append(n);
            long sum = a;
            ArrayList<Long> arrayList = new ArrayList<>();
            for (long l = n; l > 0; l--) {
                if (sum-l<0){
                    continue;
                }
                if (sum==0){
                    break;
                }
                arrayList.add(l);
                sum = sum - l;
            }
            for (Long aLong : arrayList) {
                stringBuilder.append(" ").append(aLong);    // 注意是先加空格再加数字，这样才能保证最后一个数之后没有空格
            }
            stringBuilder.append(" ");
            System.out.print(stringBuilder);
        }
    }

    private static long func(long c) {
        long x = (long) Math.sqrt(2*c);    // 根据求跟公式求出正数解
        if (x*(x+1)==2*c){    // 说明是整数解
            return x;
        }else {     // 没有整数解
            return -1;
        }
    }

}

记录踩过的坑

这一题应该是我在洛谷踩过就多的坑了。专门记录下来防止后面继续踩坑。

首先我的a和b是用int接收的，这样最后会报WA的错误，因为运算过程中结果溢出了。改成long后，我最开始的代码是用背包问题的应用来求解和为定值的多个数问题，代码如下：

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
55
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    private static LinkedList<Long> linkedList = new LinkedList<>();
    private static int count = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = bufferedReader.readLine().split(" ");
        long a = new Long(strings[0]);    // 接受a的值
        long b = new Long(strings[1]);    // 接受b的值
        long n = func(a + b);
        if (n==-1){
            System.out.println("No");
        }else {// 这一段代码是关键部分（即在连续的1,2,3...n这n个数中找到若干个数相加为a）
            // 即经典的寻找和为定值的多个数问题（背包问题的应用）
            System.out.print(n);
            sumOfkNumber(a,n);
        }

    }

    private static long func(long c) {
        long x = (long) Math.sqrt(2*c);    // 根据求跟公式求出正数解
        if (x*(x+1)==2*c){    // 说明是整数解
            return x;
        }else {     // 没有整数解
            return -1;
        }
    }

    private static void sumOfkNumber(long sum, long n) {
        // 递归出口
        if (n <= 0 || sum <= 0)
            return;
        // 输出链表
        if (sum == n) {
            if (count==0){
                StringBuilder stringBuilder = new StringBuilder(" ");
                for (Long num : linkedList) {
                    stringBuilder.append(num+ " ");
                }
                stringBuilder.append(n);  // 别忘了最后还有一个n要输出
                System.out.println(stringBuilder);
                count++;
            }
        }
        linkedList.add(n);     //典型的01背包问题
        sumOfkNumber(sum-n,n-1);    //放n，前n-1个数填满sum-n
        linkedList.remove(linkedList.size()-1);
        sumOfkNumber(sum,n-1);
    }
}

结果报Runtime Error的错。于是我把代码改进成我的题解代码，最开始还是报错。。。报的是WA错，描述为：Wrong Answer. wrong output format Unexpected character #10 , but ' ' expected。万万没想到，是我的输出语句System.out.println(stringBuilder);出了问题，因为println最后会有一个回车，改成System.out.print(stringBuilder);就通过了！

P1684 考验（洛谷提交存在问题）

题目：P1684 考验

这题目描述整那么花里胡哨的，还得翻译一下：要遵循古诗的押韵，每段四行诗的韵脚只可能是 “AABB”, “ABAB”, “ABBA” 和“AAAA”中的一种。也就是说要有两组相同的（即有一种韵脚出现四次或两种韵脚各出现两次）。而他又给不同的韵脚用1,2,3,4编号了，就变成处理相同数字的问题了。

根据题目给出的样例分析：

这里我先是用HashMap写了下，提交洛谷包Runtime Error：

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Hashtable;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = new Integer(bufferedReader.readLine());     // 接受诗的行数n
        ArrayList<Integer> arrayList = new ArrayList<>();
        // 接受n个1-4的数字
        String[] strings = bufferedReader.readLine().split(" ");
        for (String string : strings) {
            arrayList.add(new Integer(string));
        }
        /* 用HashMap来实现贪心思想,k为1-4的某一个数,v为该数出现的次数 */
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(1,0);
        hashMap.put(2,0);
        hashMap.put(3,0);
        hashMap.put(4,0);
        int count = 0;      // 用于记录循环中间出现相同次数的个数
        int result = 0;     // 最后结果（有几行诗句）
        for (int i = 0; i < n; i++) {
            hashMap.put(arrayList.get(i),hashMap.get(arrayList.get(i))+1);
            if (hashMap.get(arrayList.get(i)) == 2){    // 出现两个相同的数字
                count++;
            }
            if (count==2){  // 出现两次，有两个相同的数字
                count = 0;  // count置0
                hashMap.clear();    // 清除hashmap
                hashMap.put(1,0);
                hashMap.put(2,0);
                hashMap.put(3,0);
                hashMap.put(4,0);
                result++;
            }
        }
        System.out.println(result);
    }
}

然后我改善了一下代码，总之逻辑还是跟map类似：

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = new Integer(bufferedReader.readLine());     // 接受诗的行数n
        int[] arr = new int[n];
        // 接受n个1-4的数字
        String[] strings = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = new Integer(strings[i]);
        }
        /* */
        int count = 0;      // 用于记录循环中间出现相同次数的个数
        int result = 0;     // 最后结果（有几行诗句）
        int c1 = 0;
        int c2 = 0;
        int c3 = 0;
        int c4 = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i]==1){
                c1++;
            }else if (arr[i]==2){
                c2++;
            }else if (arr[i]==3){
                c3++;
            }else if (arr[i]==4){
                c4++;
            }
            if (c1==2){
                count++;
                c1 = 0;
            }else if (c2==2){
                count++;
                c2 = 0;
            }else if (c3==2){
                count++;
                c3 = 0;
            }else if (c4==2){
                count++;
                c4 = 0;
            }
            if (count==2){
                count = 0;
                result++;
            }
        }
        System.out.println(result);
    }
}

这次报WA的错，但是又不提供错误的测试集。我在本地运行试了好几个测试集都成功了，这里报错原因未知。