# 貪心法
by: hush
---
## 概念
----
### 貪心演算法(Greedy algorithm)
- 透過每次都選當下最優解，達到全局最優解
- **不是**所有問題都可以用貪心法解決
- 常用在最優解問題
- 遇到類似問題就大膽地猜
----
- 要寫greedy證明很重要，通常會利用反證法或是歸納法，不過比賽中的證明不需要太嚴謹
- ||不在場證明||
- ||prove by AC||
---
## 經典題目
---
### 找錢問題
----
* [csdc267](https://csdc.tw/problem/267/)
----
- 因為對所有幣值數對都是倍數關係，用目前最大面額的鈔票支付必定最佳
- 例如：
$9784=$
$9\times 1000+1\times 500+2\times 100$
$+1\times 50+3\times 10+0\times 5+4\times 1$
共$20$個貨幣
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int mny[]={500, 100, 50, 10, 5, 1};
signed main()
{
//colinorz;
int n,sum=0; cin >> n;
n=1000-(n%1000);
for (int i=0;i<6;i++)
{
sum+=n/mny[i];
n%=mny[i];
}
cout << sum << '\n';
}
```
----
:::danger
注意：若有不是倍數關係則不一定成立
:::
這時要使用dp去解決
----
練習題：
* [csdc348](https://csdc.tw/problem/348/)
----
AC code:
```cpp=
#include<bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
int pap[]={10000,5000,2000,1000},coin[]={500,100,50,10,5,1};
signed main()
{
//colinorz;
int n,ansp=0,ansc=0; cin >> n; n<<=2;
for (int i=0;i<4;i++) ansp+=n/pap[i],n%=pap[i];
for (int i=0;i<6;i++) ansc+=n/coin[i],n%=coin[i];
cout << ansp <<' '<< ansc << '\n';
}
```
---
### 堆疊問題
----
- 例題：[csdc238](https://csdc.tw/problem/238/)
- 題意：
- 有$5$本書要疊成一疊，每次取一本書要花費那本上面所有書重總和(不含自己)，取完馬上放回
- 第$i$本書重$w_i$要取$t_i$次
- 求最低搬書總花費
----
- 題解：
- $\because$ 放越上面被算到越多次
- 重量輕、拿取次數多應放上面
- $\therefore$ 合理推測$\frac{重量(w_i)}{次數(t_i)}$越小要放越上面
符合最小總花費數列的順序必滿足$\frac{w_i}{t_i}\le\frac{w_j}{t_j}, i<j$ (位置越小越上面)
結論：照著上述規則排序後算出花費即可
另解：只有5本書所以可直接枚舉排列
----
- 小技巧：
$\frac{w_i}{t_i}\le\frac{w_j}{t_j}$可以寫成$w_i\cdot t_j\le w_j\cdot t_i$
避免除法產生的浮點數運算
----
AC code:
```cpp=
#include <bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
struct book
{
int w,t;
};
bool cmp(book i,book j)
{
return i.w*j.t<j.w*i.t;
}
book a[6];
signed main()
{
//colinorz;
for (int i=0;i<5;i++) cin >> a[i].t;
for (int i=0;i<5;i++) cin >> a[i].w;
sort(a,a+5,cmp);
int sum=0,wsum=a[0].w;
for (int i=1;i<5;i++)
{
sum+=wsum*a[i].t;
wsum+=a[i].w;
}
cout << sum << '\n';
}
```
----
- 練習題：
[APCS 1710-4.物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471)
- 題解：
原理同上題(但不能枚舉了XD)
----
AC code:
```cpp=
#include <bits/stdc++.h>
#define int long long
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
struct book
{
int w,t;
};
bool cmp(book i,book j)
{
return i.w*j.t<j.w*i.t;
}
vector<book> a(100005);
signed main()
{
//colinorz;
int n; cin >> n;
for (int i=0;i<n;i++) cin >> a[i].t;
for (int i=0;i<n;i++) cin >> a[i].w;
sort(a.begin(),a.begin()+n,cmp);
int sum=0,wsum=a[0].w;
for (int i=1;i<n;i++)
{
sum+=wsum*a[i].t;
wsum+=a[i].w;
}
cout << sum << '\n';
}
```
---
### 切棍子問題
----
- [CSEC1161](https://cses.fi/problemset/task/1161/)
- 題意：
你有一條長度為$x$的棍子，你要將他切成$n$隻指定長度的棍子，長度加總起來恰為$x$。
拿起一根棍子切成兩段花費的費力是那根棍子的長度，求達成題目要求最少要花費多少力氣？
----
- 題解：
可以把題目想成要合併這$n$隻棍子，那麼越長的應該要越慢合併(減少合併次數)。
1.每次從棍子堆取出最短的兩隻
2.合併成新的棍子再丟回去棍子堆
3.重複1. 2.直到所有棍子合併完成
(要快速維護最小值可使用**heap**)
----
AC code
```cpp=
#include<bits/stdc++.h>
#define int long long
#define itn int
#define endl '\n'
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
priority_queue<int,vector<int>,greater<int>> pq;
signed main()
{
//colinorz;
int n,x,ans=0; cin >> x >> n;
for (int i=0;i<n;i++)
{
int d; cin >> d;
pq.emplace(d);
}
for (int i=0;i<n-1;i++)
{
int tmp=pq.top(); pq.pop();
tmp+=pq.top(); pq.pop();
ans+=tmp; pq.emplace(tmp);
}
cout << ans << endl;
}
```
---
### 排程問題
----
- [APCS 2301-4.機器出租](https://zerojudge.tw/ShowProblem?problemid=j608)
- 題意：
有$N$個活動，舉辦每個活動都要租借一台機器，若要舉辦第$i$個活動，就需要在時間段$[ l_i, r_i]$租借一台機器。
已知$N$個活動的需要使用的時間段，並且有$K$台機器可以開放租借，且一台機器一次只能借給一個活動，請問最多可以辦幾場活動？
----
- 題解：
- 將活動照結束時間排序
- 維護所有機器上個活動結束時間
- 遍歷所有活動，從所有$<$活動開始時間的機器結束時間中選擇最大的，並使用機器(浪費最少)
- 若無符合的機器則跳過
----
AC code:
```cpp=
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
using namespace std;
bool cmp(pii a,pii b)
{
if (a.se!=b.se) return a.se<b.se;
return a.fi<b.fi;
}
vector<pii> a(100005);
vector<int> mch(105,-1);
signed main()
{
//colinorz;
int n,k,ans=0; cin >> n >> k;
for (int i=0;i<n;i++) cin >> a[i].fi;
for (int i=0;i<n;i++) cin >> a[i].se;
sort(a.begin(),a.begin()+n,cmp);
for (int i=0;i<n;i++)
{
int slc=-1;
for (int j=0;j<k;j++)
if ( mch[j]<a[i].fi && (slc==-1||mch[j]>mch[slc]) )
slc=j;
if (slc==-1) continue;
ans++;
mch[slc]=a[i].se;
}
cout << ans << endl;
}
```
---
## 更多練習題
----
- [csdc205](https://csdc.tw/problem/205/)
- [csdc192](https://csdc.tw/problem/192/)
- [csdc316](https://csdc.tw/problem/316/)
- [zj_m603](https://zerojudge.tw/ShowProblem?problemid=m603)
- [zj_b966](https://zerojudge.tw/ShowProblem?problemid=b966)
---
# 謝謝大家
{"description":"by: hush","title":"貪心法","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":7228,\"del\":1663}]"}