Polaris6G's blog

Stay humble,stay hungry.

0%

算法基础06

Posted on Valine:

贪心问题~

  • 区间问题
  • 哈夫曼树
  • 排序不等式
  • 绝对值不等式
  • 推公式

贪心前提：是单峰问题：局部最优解 -> 全局最优解

区间问题

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

解法：

  • 将每个区间按又断电从小到大排序

  • 从前往后依次枚举每个区间

    如果当前区间中已经包含点，则直接pass

    否则，选择当前区间的右端点

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

public class Main {
	static class Range{
		public int l, r;
		public Range(int l, int r){
			this.l = l;
			this.r = r;
		}
	}
	
	static int N = 100010;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static Range[] range = new Range[N];

	public static void main(String[] args) throws IOException{
		int n = Integer.parseInt(br.readLine());
		for(int i = 0; i < n; i++) {
			String[] str = br.readLine().split(" ");
			int l = Integer.parseInt(str[0]);
			int r = Integer.parseInt(str[1]);
			range[i] = new Range(l ,r);
		}
		Arrays.sort(range, 0, n, (o1, o2) -> Integer.compare(o1.r, o2.r));
		
		int res = 0;
		int ed = (int)-2e9;
		for(int i = 0; i < n; i++) {
			if(range[i].l > ed) {
				ed = range[i].r;
				res++;
			}
		}
		System.out.println(res);
	}
}

最大不相交区间数量

给定 N 个闭区间 [ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。 输出可选取区间的最大数量。

代码与思路同上~

区间分组

给定 N 个闭区间 [ai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

1≤N≤105, −10^9≤ai≤bi≤10^9

解法：

  • 将所有区间按左端点从小到大排序

  • 从前往后处理每个区间

    判断能否将其放到某个现有的组中（l > 组内Max_r则可以)

    • 如果不存在这样的组，则开新组，然后再将其放进去

    • 如果存在这样的组，将其放进去，并更新当前组的Max_r

      如果满足条件的有多组，则可随意选择一组放入，不影响结果，这里我们可以选择Max_r最小的一组放入

  • n^2复杂度可以通过堆优化：小根堆（优先队列实现）

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

public class Main {
	static class Range{
		public int l, r;
		public Range(int l, int r){
			this.l = l;
			this.r = r;
		}
	}
	
	static int N = 100010;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static Range[] range = new Range[N];

	public static void main(String[] args) throws IOException{
		int n = Integer.parseInt(br.readLine());
		for(int i = 0; i < n; i++) {
			String[] str = br.readLine().split(" ");
			int l = Integer.parseInt(str[0]);
			int r = Integer.parseInt(str[1]);
			range[i] = new Range(l, r);
		}
		Arrays.sort(range, 0, n, (o1, o2) -> o1.l - o2.l);
		PriorityQueue<Integer> heap = new PriorityQueue<>();//默认小根堆
		
		for(int i = 0; i < n; i++) {
			if(heap.isEmpty() || heap.peek() >= range[i].l) {
				heap.add(range[i].r);
			} else {
				heap.poll();
				heap.add(range[i].r);
			}
		}
		System.out.println(heap.size());
	}
}

区间覆盖

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。 输出最少区间数，如果无法完全覆盖则输出 −1。

解法：

  • 将所有区间按左端点从小到大排序
  • 从前往后依次枚举每个区间，在所有能覆盖start的区间中，选择右端点最大的区间；然后将start更新成右端点的最大值

1≤N≤10^5, −10^9≤ai≤bi≤10^9, −10^9≤s≤t≤10^9

通过双指针来做时间复杂度为O(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
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.Arrays;

public class Main {
	static class Range{
		public int l, r;
		public Range(int l, int r){
			this.l = l;
			this.r = r;
		}
	}
	
	static int N = 100010;
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static Range[] range = new Range[N];

	public static void main(String[] args) throws IOException{
		String[] str = br.readLine().split(" ");
		int s = Integer.parseInt(str[0]);
		int t = Integer.parseInt(str[1]);
		int n = Integer.parseInt(br.readLine());
		for(int i = 0; i < n; i++) {
			str = br.readLine().split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			range[i] = new Range(a, b);
		}
		Arrays.sort(range, 0, n, (o1, o2) -> o1.l - o2.l);
		
		int res = 0;
		//双指针
		int i = 0;
		boolean flag  = false;//判断长度是否达到
		while(i < n){
			int r = (int)-2e9;
			int j = i;
			while(j < n && range[j].l <= s) {
				r = Math.max(r, range[j].r);
				j++;
			}
			res++;
			if(r < s)break;
			if(r >= t) {//必须有这个条件成立才满足题设
			    flag = true;
				break;
			}
			s = r;
			i = j;
		}
		if(flag)System.out.println(res);
		else System.out.println("-1");
	}
}

Huffman树

哈夫曼树：

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

见题：

https://www.acwing.com/problem/content/description/150/

解法：

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

时间复杂度:使用小根堆维护所有果子，每次弹出堆顶的两堆果子，并将其合并，合并之后将两堆重量之和再次插入小根堆中

每次操作会将果子的堆数减一，一共操作 n−1次即可将所有果子合并成1堆。每次操作涉及到2次堆的删除操作和1次堆的插入操作，计算量是 O(logn)。因此总时间复杂度是 O(nlogn)

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
import java.io.*;
import java.util.Queue;
import java.util.PriorityQueue;

public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine().trim());
        Queue<Integer> q = new PriorityQueue<>();
        String[] str = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            int a = Integer.parseInt(str[i]);
            q.add(a);
        }
        int res = 0;
        while(q.size() > 1){
            int a = q.peek();
            q.poll();
            int b = q.peek();
            q.poll();
            res += a + b;
            q.add(a+b);
        }
        System.out.println(res);
    }
}

排序不等式

逆序乘 <= 乱序乘 <= 顺序乘

有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.*;
import java.util.Arrays;

public class Main{
    static int N = 100010;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[] t = new int[N];
    
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            t[i] = Integer.parseInt(str[i]);
        }
        Arrays.sort(t, 0, n);
        long res = 0;
        for(int i = 0; i < n; i++){
            res += (n - i - 1) * t[i];//逆序乘最小
        }
        System.out.println(res);
    }
}

绝对值不等式

|a - x| + |b - x| >= |a - b| a <= x <= b

在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.*;
import java.util.Arrays;

public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N = 100010;
    static int[] a = new int[N];
    
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        for(int i = 0; i < n; i++){
            a[i] = Integer.parseInt(str[i]);
        }
        Arrays.sort(a, 0, n);
        long res = 0;
        for(int i = 0; i < n / 2; i++){
            res += a[n - i - 1] - a[i];
        }
        System.out.println(res);
    }
}

推公式

N 头奶牛叠罗汉，其中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。 一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。 您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

1≤N≤50000, 1≤Wi≤10,000, 1≤Si≤1,000,000,000

解法：

按照wi+si从小到大的顺序排，最大的危险系数一定是最小的

证明：（反证法）

对于第i个位置上的牛和第i+1个位置上的牛，如果有wi+si > w(i+1)+s(i+1)

分析：

i位置 i+1位置
交换前 w1+...+w(i-1) - s(i) w1+...+w(i-1)+w(i) - s(i+1)
交换后 w1+...+w(i-1) - s(i + 1) w1+...+w(i-1)+w(i+1) - s(i)

调整：

i位置 i+1位置
交换前 - s(i) w(i) - s(i+1)
交换后 - s(i + 1) w(i+1) - s(i)

再调整 + s(i + 1) + s(i)：

i位置 i+1位置
交换前 s(i + 1) w(i) + s(i)
交换后 s(i) w(i+1) + s(i + 1)

有Max[s(i+1), w(i) + s(i)] >= w(i) + s(i) >= Max(s(i), w(i + 1) + s(i +1))

交换使得Max的值向小的方向改变

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

public class Main{
    static class Pair{
        public int w, s;
        public Pair(int w, int s){
            this.w = w;
            this.s = s;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N = 50010;
    static Pair[] p = new Pair[N];
    
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++){
            String[] str = br.readLine().split(" ");
            int w = Integer.parseInt(str[0]);
            int s = Integer.parseInt(str[1]);
            p[i] = new Pair(w, s);
        }
        Arrays.sort(p, 0, n, (o1,o2) -> (o1.w + o1.s - o2.w - o2.s));
        int sum = 0;
        int res = (int)-2e9;
        for(int i = 0; i < n; i++){
            res = Math.max(res, sum - p[i].s);
            sum += p[i].w;
        }
        System.out.println(res);
    }
}