?int a[1000], b=5, c=8;
?swap(b, c); ? ?// 交換操作
?memset(a, 0, sizeof(a)); // 初始化為0或-1

引導問題

為一個小老鼠準備了M磅的貓糧，準備去和看守倉庫的貓做交易，因為倉庫里有小老鼠喜歡吃的五香豆，第i個房間有J[i] 磅的五香豆，并且需要用F[i]磅的貓糧去交換；求老鼠最多可換多少豆？若五香豆不能全換貓糧，按比例換。

Sample Input?
? 5 3 ——M貓糧? ?N房間
? 7 2 ——五香豆? 貓糧
? 4 3
? 5 2
? -1 -1 —— 結束

Sample Output
? 13.333

由按比例換，7/2=3.5? 4/3=1.333...? 5/2=2.5? 3.5最大 排序，一次換——7+5+1.3333=13.333

---

初識貪心

在對問題求解時，總是做出在當前看來是最好的選擇。

也就是說，不從整體上加以考慮，所作出的僅僅是在某種意義上的局部最優解（是否是全局最優，需要證明）。

---

例題

1.田忌賽馬

每個馬跟比自己弱的程度最小的馬

1.排序

2.藍色最大和紅色最大比較，看藍色能不能比過紅色，若比不過，拿藍色最小的跟紅色比

3.拿藍色最大跟紅色第二大的比...能比就比，不能就繼續拿最差的跟最好的比

---

反證法上大分~事件序列問題

已知N個事件的發生時刻和結束時刻。

一些在時間上沒有重疊的事件，可以構成一個事件序列，如事件{2，8，10}。

事件序列包含的事件數目，稱為該事件序列的長度。

請編程找出一個最長的事件序列。

至少存在一個最長事件序列包含最早結束事件（最早結束事件是0）

反證法證明上句：

假設所有最長事件序列都不包含最早結束事件；只要證明這個假設是錯的，原命題得證；

任取一個所謂的最長事件序列，把第一個事件去掉，換掉事件0，肯定跟后面都不沖突（因為換上的是最早結束的時間，原來都不沖突，現在更不沖突）

證明完后選中最早結束事件0? ?后面我做類似的：每次找一個最早結束的事件，只要和前面的不沖突的都選中；

---

2.搬桌子

一個公司要做調整搬桌子，房間有400個，一邊是單號，一邊雙號；

走廊很窄，只通過1個桌子過；

輸入：

第二行：趟數

第三行：房間號：10號搬到20號

每趟搬要10min：不重疊可以同時搬，要10min；重疊要分開搬

法一：與上題的思想差不多，只不過，改成了最早開始事件（找開始最早的）

法二：統計每個區間在時間軸上的重疊次數，并找出最大重疊次數的區間。

#include <bits/stdc++.h>
using namespace std;int main() {int t, i, j, N, P[200];  // t是測試用例的數量，N是每個測試用例的區間數量int s, d, temp, k, MAX;  // s和d是區間的起點和終點，MAX用于記錄最大重疊次數cin >> t;for (i = 0; i < t; i++) {// 初始化P數組，用于記錄每個時間點的重疊次數for (j = 0; j < 200; j++)P[j] = 0;cin >> N;  // 讀取當前測試用例的區間數量for (j = 0; j < N; j++) {cin >> s >> d;  // 讀取區間的起點和終點s = (s - 1) / 2;  // 將起點轉換為數組索引d = (d - 1) / 2;  // 將終點轉換為數組索引// 如果起點大于終點，交換它們if (s > d) {temp = s;s = d;d = temp;}// 在區間[s, d]內的每個時間點增加計數for (k = s; k <= d; k++)P[k]++;}// 找到最大重疊次數MAX = -1;for (j = 0; j < 200; j++)if (P[j] > MAX)MAX = P[j];// 輸出最大重疊次數乘以10cout << MAX * 10 << endl;}return 0;
}

---

3.刪數問題

已知一個長度不超過240位的正整數n（其中不含有效字0），去掉其中任意s（s小于n的長度）個數字后，將剩下的數字按原來的左右次序組成一個新的正整數。

給定n和s，請編程輸出最小的新正整數。

Sample Input
178543 4
Sample Output
13

法一：從左到右掃描逆序對，刪掉左邊的數，若沒有逆序對，刪掉最后一位數

1 7?8 5?4 3 —— 1 7 5 4 3 ——1 5 4 3 ——1 4 3 —— 1 3?

1 2 3 4?

---

4.青蛙的鄰居

每個湖泊都有一個青蛙，如果兩個湖泊之間有水渠相連，我們認為兩個青蛙他們為鄰居；

問：你可以畫出這個湖泊分布圖嗎？

Sample Input

3

7 —— 青蛙個數

4 3 1 5 4 2 1 —— 第一個青蛙有4個鄰居；第二個青蛙有3個鄰居....

6

4 3 1 4 2 0

6

2 3 1 1 2 1?

Sample Output

YES

NO

YES

?用以下知識可解決：

---

離散數學：可圖性判定?

兩個概念：

1.度序列：若把圖A所有頂點的度數排成一個序列S，則稱S為圖A的度序列。

度：一個頂點他有幾條邊，度就是幾

2 3 1 1 1 就是度序列

2.序列是可圖的：一個非負整數組成的有限序列如果是某個無向圖的度序列，則稱該序列是可圖的。

若度序列2 3 1 1 1可以畫出圖A，就是可圖的；

---

Havel-Hakimi定理：解決可讀性判定

之后再排序：3 2 2 2 1

做一趟，排序一次；只要出現負數，就不可能了，圖畫不出來；最后全變成0，可以畫；

Havel定理的解釋——加加減減與圖的對應關系_嗶哩嗶哩_bilibili

---

特別說明

若要用貪心算法求解某問題的整體最優解，必須首先證明貪心思想在該問題的應用結果就是最優解！！

在使用貪心算法解決問題時，必須首先證明貪心策略能夠導致整體最優解。貪心算法通常通過每一步選擇局部最優解來構建全局解，但并非所有問題都適合使用貪心算法，因此證明其正確性是關鍵。

說明理由：

若某貨幣系統有三種幣值，分別為一角、五分和一分；要找1角5分
求最小找幣數時，是否可以用貪心法求解？

可以；先用最大的能找幾個找幾個；

如果將這三種幣值改為一種一分、五分和一分；要找1角5分

是否還可以使用貪心法求解？

不行；

因為他不成倍數；

貪心算法的常見操作：

貪心總是要找最大的、最小的、最劃算的，往往要排序；