2
贪心算法篇——经典题型 - 秋落雨微凉
source link: https://www.cnblogs.com/qiuluoyuweiliang/p/16931256.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
贪心算法篇——经典题型
本次我们介绍贪心算法篇的经典题型，我们会从下面几个角度来介绍：
- Huffman树
- 排序不等式
- 绝对值不等式
Huffman树
我们直接给出对应题型：
/*题目名称*/
合并果子
/*题目介绍*/
在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。
达达决定把所有的果子合成一堆。
每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。
可以看出，所有的果子经过 n−1 次合并之后，就只剩下一堆了。
达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。
假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达达耗费的体力最少，并输出这个最小的体力耗费值。
例如有 3 种果子，数目依次为 1，2，9。
可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。
所以达达总共耗费体力=3+12=15。
可以证明 15 为最小的体力耗费值。
/*输入格式*/
输入包括两行，第一行是一个整数 n，表示果子的种类数。
第二行包含 n 个整数，用空格分隔，第 i 个整数 ai 是第 i 种果子的数目。
/*输出格式*/
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。
输入数据保证这个值小于 231。
/*数据范围*/
1 ≤ n ≤ 10000,
1 ≤ ai ≤ 20000
/*输入样例*/
3
1 2 9
/*输出样例*/
15
我们采用贪心的思想来进行分析：
/*贪心思想*/
我们在当前情况以最优解的形式给出结果
/*题目分析*/
我们仅针对当前情况进行分析，如果我们想要得到当前情况的体力耗费最小值
那么我们只需要找到该果子中最小的两堆，进行合并即可
我们直接给出求解代码：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int N = 10010;
int n = scanner.nextInt();
// 我们这里直接采用一个优先队列来存储，直接将其变为从小到大排列的方式
Queue<Integer> minheap = new PriorityQueue<>();
// 输入数据
for(int i = 0 ; i < n ; i ++ ){
int x = scanner.nextInt();
minheap.add(x);
}
// 这是我们的最后返回结果
int res = 0;
// 我们循环n次，就相当于将n堆果子合并n次
for(int i = 0 ; i < n ; i ++ ){
// 这里需要判断大小，当大小大于1时，我们再合并，因为当大小为1时就是结果了
if(minheap.size() > 1){
// 将最小的数取出来后弹出
int a = minheap.poll();
//将第二小的数取出来后弹出
int b = minheap.poll();
// 将每一次两堆最小值相加之后的加过累加
res += a + b;
//然后将他放入到堆中
minheap.add(a + b);
}
}
// 最后输出结果即可
System.out.println(res);
}
}
排序不等式
我们直接给出对应题型：
/*题目名称*/
排队打水
/*题目介绍*/
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
/*输入格式*/
第一行包含整数 n。
第二行包含 n 个整数，其中第 i 个整数表示第 i 个人装满水桶所花费的时间 ti。
/*输出格式*/
输出一个整数，表示最小的等待时间之和。
/*数据范围*/
1 ≤ n ≤ 105,
1 ≤ ti ≤ 104
/*输入样例*/
7
3 6 1 4 2 5 7
/*输出样例*/
56
我们采用贪心的思想来进行分析：
/*贪心思想*/
我们在当前情况以最优解的形式给出结果
/*题目分析*/
我们仅针对当前情况进行分析，如果我们想要得到当前状况后续等待时间最少
那么我们只需要找到耗时最少的人，那么后面的人等待时间就是最少的
我们直接给出求解代码：
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 ++ ){
// 我们直接计算该时间段后面的人所需要等待的总时间（n-1-i是指当前排队人数，w[i]是当前耗费时间，+=即可统计）
res += w[i] * (n - i - 1);
}
System.out.println(res);
}
}
绝对值不等式
我们直接给出对应题型：
/*题目名称*/
货仓选址
/*题目介绍*/
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
/*输入格式*/
第一行输入整数 N。
第二行 N 个整数 A1∼AN。
/*输出格式*/
输出一个整数，表示距离之和的最小值。
/*数据范围*/
1 ≤ N ≤ 100000,
0 ≤ Ai ≤ 40000
/*输入样例*/
4
6 2 9 1
/*输出样例*/
12
我们采用贪心的思想来进行分析：
/*贪心思想*/
我们在当前情况以最优解的形式给出结果
/*题目分析*/
我们仅针对当前情况进行分析
我们如果只有两家商家，那么只要在他俩之间的点都可以保证两者到货舱距离和的最小值
但是当出现三家商家时，我们首先无法使用前面的思想了
这时我们会发现如果货舱在两边的商家中间时，两边商家到该货舱的距离为最小且不改变，这时我们只需要保证货舱到中间的商家距离最小即可
那么该货舱的位置肯定就是中间的商家位置了
那么我们就直接拟设一个点，设为最中间商家的点并尝试获得答案（贪心就是不断猜测并验证的过程）
我们直接给出求解代码：
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]);
}
System.out.println(sum);
}
}
我们直接给出对应题型：
/*题目名称*/
耍杂技的牛
/*题目介绍*/
农民约翰的 N 头奶牛（编号为 1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。
奶牛们不是非常有创意，只提出了一个杂技表演：
叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。
奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。
这 N 头奶牛中的每一头都有着自己的重量 Wi 以及自己的强壮程度 Si。
一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。
您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。
/*输入格式*/
第一行输入整数 N，表示奶牛数量。
接下来 N 行，每行输入两个整数，表示牛的重量和强壮程度，第 i 行表示第 i 头牛的重量 Wi 以及它的强壮程度 Si。
/*输出格式*/
输出一个整数，表示最大风险值的最小可能值。
/*数据范围*/
1 ≤ N ≤ 50000,
1 ≤ Wi ≤ 10,000,
1 ≤ Si ≤ 1,000,000,000
/*输入样例*/
3
10 3
2 5
3 3
/*输出样例*/
2
我们采用贪心的思想来进行分析：
/*贪心思想*/
我们在当前情况以最优解的形式给出结果
/*题目分析*/
我们如果直接按数值排序，因为存在两个数值，我们是无法找到规律的
但是我们可以进行推算：（危险系数设计为a[i]）
我们最开始按照顺序进行排列，那么他们的危险系数为：
a[i] = w[1]+w[2]+...+w[i-1]-s[i]
a[i+1] = w[1]+w[2]+...+w[i]-s[i+1]
我们采用贪心算法，我们如果每次将第i头牛和第i+1头牛进行位置转换，那么是否可以缩减危险系数：
a[i] = w[1]+w[2]+...+w[i-1]+w[i+1]-s[i]
a[i+1] = w[1]+w[2]+...+w[i-1]-s[i+1]
我们如果抛出掉多余元素：
a[i] 交换前：-s[i]
a[i+1]交换前：w[i]-s[i+1]
a[i] 交换后：w[i+1]-s[i]
a[i+1]交换后：-s[i+1]
我们只需要比较MAX即可，同时由于w[i],s[i]均大于0，我们可以进行推算（推算步骤这里不演示了）：
- 当s[i]+w[i] > s[i+1]+w[i+1]时，进行交换，我们的危险系数可以下降或者不变
那么我们只需要将牛按照s[i]+w[i]的数值进行排序，并最后计算出对应值危险系数值即可
我们直接给出求解代码：
import java.util.*;
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);
}
}
// 模拟牛，主要是为了更换CompareTo比较条件
class PII implements Comparable<PII>{
int x,y;
public PII(int x,int y){
this.x = x;
this.y = y;
}
// 注意传参， 我们这里的x是指体重+强壮值，还因为我们需要从上往下计算，所以我们以体重+强壮值从小到大排序
public int compareTo(PII o){
return Integer.compare(x,o.x);
}
}
好的，关于贪心算法篇的经典题型就介绍到这里，希望能为你带来帮助~
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK