本次我們介紹貪婪演演算法篇的經典題型，我們會從下面幾個角度來介紹：
我們直接給出對應題型：
/*題目名稱*/
合併果子
/*題目介紹*/
在一個果園裡，達達已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆。
達達決定把所有的果子合成一堆。
每一次合併，達達可以把兩堆果子合併到一起，消耗的體力等於兩堆果子的重量之和。
可以看出，所有的果子經過 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);
}
}
好的，關於貪婪演演算法篇的經典題型就介紹到這裡，希望能為你帶來幫助~