貪心演算法(Greedy algorithm)
特性:
- 算法由一連串決定組成(由大到小逐一考慮各種代幣的數量)，每次考慮當前最好
決定(能換盡量換)，選擇後就不再更改。
- 算法的正確性必須經過證明，內容就是要證明所下的決定是對的，也就是一定有一
個最佳解包含了貪心法所做的決定，而證明的方法通常都是用換的：假設有一個最
佳解跟貪心法做的決定不一樣，那麼，我們可以換成一個與貪心法一樣的決定，而
解會更好，或至少不會變差。
note:個人覺得貪心是必須在數學規律上下功夫，找到題目的特性，所以貪心是程式簡單，但想出規律卻是難的
優先佇列(priority_queue)
- top會是最大值
- 如果要讓top為最小值可以加上負號讓大小關係反轉
priority_queue<pair<int,int>> pq; 會先比對pair的first- 加入新元素(push)，O(log(n))
- 查詢最大值(top)，O(1)
- 刪除最大值(pop)，O(log(n))
- 檢查是否為空(empty)，O(1)
- 比set快兩倍以上!!!
例題 P-4-2. 笑傲江湖之三戰
https://judge.tcirc.tw/problem/d043
都是用貪心算法，找到最優解法
自己寫:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a<b;
}
int main()
{
int n;
cin>>n;
int temp;
int ans=0;
deque<int>pq1;
deque<int>pq2;
for(int i=0;i<n;i++){
cin>>temp;
pq2.push_back(temp);
}
for(int i=0;i<n;i++){
cin>>temp;
pq1.push_back(temp);
}
sort(pq1.begin(),pq1.end(),cmp);
sort(pq2.begin(),pq2.end(),cmp);
while(!pq1.empty()){
if(pq1.front()>pq2.front()){
pq1.pop_front();
pq2.pop_front();
ans++;
}else{
pq1.pop_front();
pq2.pop_back();
}
}
cout<<ans;
return 0;
}
|
例題 P-4-3. 十年磨一劍 (最少完成時間)
https://judge.tcirc.tw/problem/d044
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
typedef long long LL;
using namespace std;
int main()
{
LL n;
cin>>n;
priority_queue<LL,vector<LL>,greater<LL>> pq;
LL temp;
for(LL i=0;i<n;i++){
cin>>temp;
pq.push(temp);
}
LL ans=0;
temp=0;
for(LL i=0;i<n;i++){
temp+=pq.top();
pq.pop();
ans+=temp;
}
cout<<ans;
return 0;
}
|
P-4-4. 幾場華山論劍(activity selection)
https://judge.tcirc.tw/problem/d045
「若[x,y]是所有現存線段中右端點最小的，那麼一定有個最佳解是挑選了[x,y]。」
證明：假設最佳解沒有挑[x,y]，令[a,b]是最佳解中右端點最小的。根據我們的假設，
y <= b，因此將[x,y]取代[a,b]不會重疊到任何最佳解中的其他線段，我們可以得到
另外一個最佳解包含[x,y]。
根據此性質，我們可以不斷地將最小右端的線段挑選進解答，然後略過任何與它重疊的
線段。因為線段不會改變，一開始依照右端由小排到大，然後從頭到尾掃描一次就可以
得到答案。
自己寫:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
typedef long long LL;
using namespace std;
struct act{
int l;
int r;
};
bool cmp(act a,act b){
return a.r<b.r;
}
int main()
{
int n;
LL temp1,temp2;
act s[100010];
cin>>n;
for(int i=0;i<n;i++){
cin>>s[i].l>>s[i].r;
}
sort(s,s+n,cmp);
LL ans=1;
temp1=s[0].r;
for(int i=1;i<n;i++){
if(temp1<s[i].l){
temp1=s[i].r;
ans++;
}
}
cout<<ans;
return 0;
}
|
P-4-5. 嵩山磨劍坊的問題(加權最小完成時間)
https://judge.tcirc.tw/problem/d046
有權重的問題都要繞彎……
重點是數學上加權的比較，觀察發現t/w的數值越小應該要排在越前面
證明:
經過推導:變化量=W[i]t[i+1]-w[i+1]*t[i]
假設t[i]/w[i] > t[i+1]/w[i+1] 交叉相乘得到
w[i+1]*t[i]<t[i+1]*w[i] 運算
w[i]*t[i+1]-w[i+1]*t[i]<0 也就是變化量為負，交換解會更好
自己寫:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<bits/stdc++.h>
typedef long long LL;
using namespace std;
bool cmp(pair<int,int>a,pair<int,int>b){
return a.first*b.second<b.first*a.second;
}
int main(){
int n;
cin>>n;
LL temp;
deque<pair<int,int>>dq;
for(int i=0;i<n;i++){
cin>>temp;
dq.push_back({temp,0});
}
for(int i=0;i<n;i++){
cin>>temp;
dq[i]={dq[i].first,temp};
}
sort(dq.begin(),dq.end(),cmp);
LL total=0;
temp=0;
for(auto t:dq){
temp+=t.first;
total+=temp*t.second;
}
cout<<total;
return 0;
}
|
Q-4-6. 少林寺的自動寄物櫃 (APCS201710)
習題
發現要自己推導出數學規律是十分困難且耗時的，而且很需要數感的天分，以後寫到背包問題後再重新寫一次看看。
自己寫:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
typedef long long LL;
using namespace std;
bool cmp(pair<int,int> a,pair<int,int> b){
return a.first*b.second<b.first*a.second;
}
int main(){
int n;
cin>>n;
LL temp;
deque<pair<int,int>> dq;
for(int i=0;i<n;i++){
cin>>temp;
dq.push_back({temp,0});
}
for(int i=0;i<n;i++){
cin>>temp;
dq[i]={dq[i].first,temp};
}
sort(dq.begin(),dq.end(),cmp);
temp=0;
LL ans=0;
bool valid=true;
for(auto t:dq){
if(valid){
valid=false;
temp+=t.first;
continue;
}
ans+=temp*t.second;
temp+=t.first;
}
cout<<ans;
return 0;
}
|