贪心算法 入门题集

贪心算法

贪心算法思路：找到局部最优解->推全局最优解
一般贪心算法需要排序找到每次最“贪心”的权值

一、区间问题：

对右端点进行排序

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.*;
public class Main{
    static int N = (int)1e5 5;
    static int arr[][] = new int[N][2];
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i = 0 ; i < n  ;   i){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        //  对右端点进行排序
        Arrays.sort(arr,0,n,new Comparator<int[]>() { 
		        	@Override
		        	public int compare(int[] o1, int[] o2) {
		        			return o1[1] - o2[1];
		        	}
		        });

        int ed = Integer.MIN_VALUE;
        int cnt = 0;
        //  贪心
        for(int i = 0 ; i < n ;   i){
            if(arr[i][0] > ed){
                cnt  ;
                ed = arr[i][1];
            }

        }
        System.out.println(cnt);
    }
}

import java.io.*;
import java.util.Comparator;
import java.util.*;
public class Main{
    static int N = (int)1e5 5;
    static int arr[][] = new int[N][2];
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        for(int i = 1 ; i<= n ; i  ){
            arr[i][0]  = sc.nextInt();
            arr[i][1]  = sc.nextInt();
        }
        Arrays.sort(arr, 1,n 1,new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // for(int i = 1 ; i <= n ;i  ){
        //     System.out.println( arr[i][0]  " -> "  arr[i][1]);
        // }
        q.add(arr[1][1]);
        for (int i = 2; i <= n  ; i  ) {
            if(arr[i][0] > q.peek()){
                int max_r = arr[i][1];
                q.poll();
                q.add(max_r);
            }else {
                int max_r = arr[i][1];
                q.add(max_r);
            }
        }
        System.out.println(q.size());
    }
}

import java.io.*;
import java.util.Comparator;
import java.util.*;
public class Main{
    static int N = (int)1e5 5;
    static int arr[][] = new int[N][2];
    // static PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1]-o2[1]);
    public static void main(String[] args){
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int l = sc.nextInt();
        int r = sc.nextInt();
        int n = sc.nextInt();
        for(int i = 1 ; i<= n ; i  ){
            arr[i][0]  = sc.nextInt();
            arr[i][1]  = sc.nextInt();
        }
        Arrays.sort(arr, 1,n 1,new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        // for(int i = 1 ; i <= n ;i  ){
        //     System.out.println( arr[i][0]  " -> "  arr[i][1]);
        // }
        // q.add(arr[0]);
        int ans = 0;
        int st =  l ; 
        for (int i = 1; i <= n;) {
            int m_r = -0x3f3f3f3f;
            if(arr[i][0] > st ){
                System.out.println(-1);
                return ;
            }
            while(i <= n && arr[i][0] <= st ){
                m_r = Math.max(m_r , arr[i][1]);
                i  ;
            }
            // System.out.println(m_r);
            st = m_r;
            ans  ;
            if(st >= r){
                System.out.println(ans);
                return ;
            }
        }
        System.out.println(-1);

    }
}

二 、Haffman Tree

ACwing \148. 合并果子

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

达达决定把所有的果子合成一堆。

每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。

可以看出，所有的果子经过 n−1n−1 次合并之后，就只剩下一堆了。

达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为 11，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。

例如有 33 种果子，数目依次为 1，2，91，2，9。

可以先将 1、21、2 堆合并，新堆数目为 33，耗费体力为 33。

接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 1212，耗费体力为 1212。

所以达达总共耗费体力=3 12=15=3 12=15。

可以证明 1515 为最小的体力耗费值。

输入格式

输入包括两行，第一行是一个整数 nn，表示果子的种类数。

第二行包含 nn 个整数，用空格分隔，第 ii 个整数 aiai 是第 ii 种果子的数目。

输出格式

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。

输入数据保证这个值小于 231231。

数据范围

1≤n≤100001≤n≤10000,
1≤ai≤200001≤ai≤20000

输入样例：

3 
1 2 9 

输出样例：

15
思路：将权值小的点放入haffman层数最深的位置可以保证每次的体力消耗值是最小的

import java.io.*;
import java.util.*;
public class Main{
    static int N = (int)1e4 5;
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        for(int i = 1 ; i<= n ; i  ){
            q.add(sc.nextInt());
        }
        int res =  0;
        while(q.size()>1){
            int a = q.poll();
            int b = q.poll();
            res  = a  b;
            q.add(a b);
        }
        
        System.out.println(res);
        
    }
}

三、区间不等式

913. 排队打水

有 nn 个人排队到 11 个水龙头（领头）（领头）处打水，第 ii 个人装满水桶所需的时间是 titi，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

输入格式

第一行包含整数 n。

第二行包含 n 个整数，其中第 i个整数表示第 i个人装满水桶所花费的时间 ti。

输出格式

输出一个整数，表示最小的等待时间之和。

数据范围

1≤n≤1051≤n≤105,
1≤ti≤1041≤ti≤104

输入样例：

7
3 6 1 4 2 5 7

输出样例：

56

有 nn 个人排队到 11 个水龙头（领头）（领头）处打水，第 ii 个人装满水桶所需的时间是 titi，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

输入格式

第一行包含整数 nn。

第二行包含 nn 个整数，其中第 ii 个整数表示第 ii 个人装满水桶所花费的时间 titi。

输出格式

输出一个整数，表示最小的等待时间之和。

数据范围

1≤n≤1051≤n≤105,
1≤ti≤1041≤ti≤104

输入样例：

7
3 6 1 4 2 5 7

输出样例：

56

import java.io.*;
import java.util.*;
public class Main{
    static int N = (int)1e4 5;
    static PriorityQueue<Integer> q = new PriorityQueue<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        for(int i = 1 ; i<= n ; i  ){
            q.add(sc.nextInt());
        }
        long res =  0;
        while(q.size()>1){
            int a = q.poll();
            res  = a * (q.size());
        }
        
        System.out.println(res);
        
    }
}

绝对值不等式

思路：可以得出当选仓地址位于数组中位数位置时，仓到各个点的距离之和为最小值。初中距离问题

1）对数组进行排序
2）找到数组中位数位置
3）循环得到ans

import java.util.*;
import java.io.*;
public class Main{
    static int  N  = (int) 1e5 10;
    static int[] arr = new int[N];
    static int n;
    public static void main(String[] args ){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        n = in.nextInt();
        for(int i = 1 ; i <= n ; i   ){
            arr[i]= in.nextInt();
        }
        Arrays.sort(arr,1,n 1);
        int mid = arr[(n 1)>>1];
        int res = 0;
        for(int i = 1 ; i <= n ; i   ){
            res  = Math.abs(mid - arr[i]);
        }
        System.out.println(res);
    }
}

推公式

分析：

设
w i s i > w ( i 1 ) s ( i 1 ) w_i s_i > w_(i 1) s_(i 1) wi si>w(i 1) s(i 1)
可以推出一下：

上下消元，并同时加上
$$s[i]s[i1]$$
得到

**由此可以看出：一从大到小的顺序排列时，交换前后两牛的位置会使得 交换后(i 1 与 i 位置上)的值变小 **

由此，我们从小到大对s_i w_i 进行排序 即可得出贪心的最小值。

import java.util.*;
import java.io.*;
class Cow implements Comparable<Cow> {
    int s ;
    int w ;
    int sum ;
    public Cow(int w , int s ){
        this.s = s ;
        this.w = w;
        this.sum = s   w;
    }
    @Override
    public int compareTo(Cow o) {
        return sum - o.sum;
    }
}
public class Main{
    
    static int  N  = (int) 1e5 10;
    static Cow[] cow = new Cow[N];
    static int n;
    public static void main(String[] args ){
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        n = in.nextInt();
        for(int i = 1 ; i <= n ; i   ){
            int w = in.nextInt();
            int s = in.nextInt();
            cow[i]= new Cow(w,s);
        }
        Arrays.sort(cow,1,n 1);
        long res = -0x3f3f3f3f;
        long sum = 0 ;
        cow[0] = new Cow(0,0);
        for(int i = 1 ; i <= n ; i   ){
            // System.out.println(cow[i].w   " : "   cow[i].s   " : "   cow[i].sum);
            sum  = cow[i-1].w;
            res = Math.max(res,sum-cow[i].s);
        }
        System.out.println(res);
    }
}

这篇好文章是转载于：学新通技术网