✔ ★ 算法基础笔记（Acwing）（六）—

✔ ★ 算法基础笔记（Acwing）（六）—— 贪心【java版本】

贪心

一、区间问题
- - - 1. 区间选点
    - 2. 最大不相交区间数量
    - 3. 区间分组(用堆top 代表区间头头)
    - - POJ3614Sunscreen(优先队列+贪心)
    - 4. 区间覆盖
二、哈夫曼树
- - - 1. 合并果子
三、排序不等式
- - - 1. 排队打水
四、绝对值不等式
- - - 货仓选址
五、推公式
- - - 耍杂技的牛

一、区间问题

1. 区间选点

原题链接
原题链接
在这里插入图片描述

import java.util.*;
class Range implements Comparable<Range>{int l,r;public Range(int l,int r){this.l = l;this.r = r;}public int compareTo(Range o){return Integer.compare(r,o.r);//return this.r - o.r;}
}
public class Main{static int N = 100010,INF = 0x3f3f3f3f,n;static Range[] range = new Range[N];//结构体创建数组需要定义成全局变量public static void main(String[] args){Scanner scan = new Scanner(System.in);n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){int l = scan.nextInt();int r = scan.nextInt();range[i] = new Range(l,r);}//结构体排序Arrays.sort(range,0,n); //Arrays.sort(range, 0, n, (o1, o2) -> o1.r - o2.r);int res = 0;//表示一共需要多少点int ed = -INF; // 上一个点的右端点for(int i = 0 ; i < n ; i ++ ){if(range[i].l > ed){res ++ ;ed = range[i].r;}}System.out.println(res);}
}

2. 最大不相交区间数量

原题链接
原题链接

import java.util.*;
class Range implements Comparable<Range>{int l,r;public Range(int l,int r){this.l = l;this.r = r;}public int compareTo(Range o){return Integer.compare(r,o.r);//return this.r - o.r;}
}
public class Main{static int N = 100010,INF = 0x3f3f3f3f,n;static Range[] range = new Range[N];//结构体创建数组需要定义成全局变量public static void main(String[] args){Scanner scan = new Scanner(System.in);n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){int l = scan.nextInt();int r = scan.nextInt();range[i] = new Range(l,r);}//结构体排序Arrays.sort(range,0,n); //Arrays.sort(range, 0, n, (o1, o2) -> o1.r - o2.r);int res = 0;//表示一共需要多少点int ed = -INF; // 上一个点的右端点for(int i = 0 ; i < n ; i ++ ){if(range[i].l > ed){res ++ ;ed = range[i].r;}}System.out.println(res);}
}

3. 区间分组(用堆top 代表区间头头)

原题链接
原题链接

POJ3614Sunscreen(优先队列+贪心)

原题链接

import java.util.*;
class Range implements Comparable<Range>{int l,r;public Range(int l,int r){this.l = l;this.r = r;}public int compareTo(Range o){return Integer.compare(l,o.l);}
}
public class Main{static int N = 100010,n;static Range[] range = new Range[N];public static void main(String[] args){Scanner scan = new Scanner(System.in);n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){int l = scan.nextInt();int r = scan.nextInt();range[i] = new Range(l,r); }Arrays.sort(range,0,n);PriorityQueue<Integer> minheap = new PriorityQueue<>(); // 小根堆for(int i = 0 ; i < n ; i ++ ){Range r = range[i];//小根堆的最小值要大于等于。因为相等也是有交点if(minheap.isEmpty() || minheap.peek() >= r.l) minheap.add(r.r);else{minheap.poll();minheap.add(r.r);}}System.out.println(minheap.size());}
}

4. 区间覆盖

原题链接
原题链接

import java.util.*;
class Range implements Comparable<Range>{int l,r;public Range(int l,int r){this.l = l;this.r = r;}public int compareTo(Range o){return Integer.compare(l,o.l);}
}
public class Main{static int N = 100010;static Range[] range = new Range[N];public static void main(String[] args){Scanner scan = new Scanner(System.in);int st = scan.nextInt();int ed = scan.nextInt();int n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){int l = scan.nextInt();int r = scan.nextInt();range[i] = new Range(l,r);}Arrays.sort(range,0,n);int res = 0;//答案boolean success = false;//表示成功for(int i = 0 ; i < n ; i ++ ){ // 使用双指针算法，来查找每个 <= st的右端点最长的数int j = i;int end = (int)-(2e9);while(j < n && range[j].l <= st){ // 将所有左端点小于st的数的右端点进行比较，取出最大值end = Math.max(end,range[j].r);j ++ ;}if(end < st)  break; //如果右端点最大的点还小于st的话，就说明覆盖不完整，无解了breakres ++; // 进行到这里就是有一个区间了 +1if(end >= ed){ // 如果进行到这一步完全覆盖了，就标记一下，然后breaksuccess = true;break;}st = end;//没选取一个区间，就将st赋值成这个区间的右端;i = j - 1; //然后将因为我们j是判断了所有的第一个可以选的区间，//所以将这些都不用看了，直接从j开始看，i= j，因为是从0开始的，所以就赋值成j - 1}if(!success) res = -1; //如果没有标记就是说明没有完全覆盖，将结果复制成-1System.out.println(res);//最后输出res}
}

二、哈夫曼树

1. 合并果子

原题链接
原题链接
在这里插入图片描述

import java.util.*;
public class Main{public static void main(String[] args){Scanner scan = new Scanner(System.in);int N = 10010;int n = scan.nextInt();Queue<Integer> minheap = new PriorityQueue<>();for(int i = 0 ; i < n ; i ++ ){int x = scan.nextInt();minheap.add(x);}int res = 0;for(int i = 0 ; i < n ; i ++ ){if(minheap.size() > 1){ // 为什么是大于1呢，如果剩余一组就说明是最后的结果了int a = minheap.poll(); // 将最小的数取出来后弹出int b = minheap.poll(); //将第二小的数取出来后弹出res += a + b;   // 将每一次两堆最小值相加之后的加过累加minheap.add(a + b);//然后将他放入到堆中}}System.out.println(res);}
}

三、排序不等式

1. 排队打水

原题链接
原题链接

import java.util.*;
public class Main{public static void main(String[] agrs){Scanner scan = new Scanner(System.in);int N = 100010;int[] w = new int[N];int n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){w[i] = scan.nextInt();}Arrays.sort(w,0,n);long res = 0;for(int i = 0 ; i < n ; i ++ ){res += w[i] * (n - i - 1);}System.out.println(res);}
}

四、绝对值不等式

货仓选址

原题链接
原题链接

import java.util.*;
public class Main{public static void main(String[] agrs){Scanner scan = new Scanner(System.in);int N = 100010;int[] a = new int[N];int n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){a[i] = scan.nextInt();}Arrays.sort(a,0,n);int sum = 0;for(int i = 0 ; i < n ; i ++ ){sum += Math.abs(a[i] - a[n / 2]); // Math.abs -- 求绝对值}System.out.println(sum);}
}

五、推公式

耍杂技的牛

原题链接
原题链接

import java.util.*;
class PII implements Comparable<PII>{int x,y;public PII(int x,int y){this.x = x;this.y = y;}public int compareTo(PII o){return Integer.compare(x,o.x);}
}
public class Main{static int N = 50010;static PII[] p = new PII[N];static int[] s = new int[N];public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();for(int i = 0 ; i < n ; i ++ ){int w = scan.nextInt();int s = scan.nextInt();p[i] = new PII(w + s,w); // 存入（体重+强壮值，体重）}Arrays.sort(p,0,n);int res = (int) -1e9;int sum = 0;for(int i = 0 ; i < n ; i ++ ){int w = p[i].y; // 体重int s = p[i].x - w; // 强壮值res = Math.max(res,sum - s); // 减去的是最下面的一个人的强壮值sum += w; //叠罗汉上去一个人就得叠加重量}System.out.println(res);}
}