【算法】贪心算法

贪心算法在解决问题上的策略就是每次选取局部最优, 无论将来有什么结果, 这个选择都不会改变, 贪心算法能够获得近似最优解, 所以在使用贪心算法时要尝试去证明可行或者亲自去跑一下样例.

霍夫曼编码

霍夫曼编码其实也是一种贪心策略, 霍夫曼编码在每次编码时都会对出现频数少的字符进行编码, 示意图:

通过每次对最少频数的字符编码来构造一颗霍夫曼树, 在最后高频词的字符就会被分配到短的二进制码.

例题:

题目就是霍夫曼编码的模板题, 优先挑选消耗体力少的果子合并, 避免重复对消耗体力多的果子合并.

这里要注意的是如何通过代码去构造霍夫曼编码, 用到的方法是 STL 中的 priority_queue , 构建一个小根堆, 每次合并完后 pop 掉合并的两个元素, 在 push 合并后的元素即可.

代码:

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
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int main(){
int n;
cin>>n;
priority_queue<int, vector<int>, greater<int>> heap
for(int i=0;i<n;i++){
int x;
cin>>x;
heap.push(x);
}
int res=0;
while(heap.size()>1){
int x = heap.top();
heap.pop();
int y = heap.top();
heap.pop();
res += x+y;
heap.push(x+y);
}
cout<<res<<endl;
return 0;
}

区间调度问题

区间调度问题大部分情况是使用动态规划去做, 但是贪心在证明正确性后也可以去解决区间调度问题, 例题:

这道题就是要在有限时间内尽量完成多的事, 这里可以去构思谈心策略:

  • 最短时间优先: 不可行, 如果按照最短时间的话可能会产生空隙.
  • 最早开始优先: 不可行, 如果一个节目最早开始但是持续很久, 也不会是最优策略
  • 最早结束优先: 可行

这里就采用最早结束优先策略, 在写代码的时候要构造一个 pair 去记录开始时间和结束时间, 以便解决区间覆盖问题.

代码:

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<iostream>
#include<vector>
#include<algorithm>
vector<<int,int>> TVs;
int main(){
int n;
for(int i=0;i<n;i++){
int start, end;
cin>>start>>end;
// 这里将 end 写在前面可以不用重构 cmp
TVs.push_back(make_pair(end,start));
}
sort(TVs.begin(),TVs.end());
int res=1;
int tmp=0;
for(int i=1;i<=n;i++){
if(TVs[i].second >= TVs[tmp].first){
tmp = i;
res++;
}
}
cout<<res<<endl;
return 0;
}

再来看一道例题:

这道题由于奶牛到了一定要挤奶, 所以区间是无法变动的, 一定要安排一个栅栏给他, 这道题中的贪心策略就是时间开始早的先安排, 如果有空的就给他安排上, 没空的就再开一个栅栏.

代码的关键点就是要写一个结构体去记录奶牛的产奶时间, 结束时间和奶牛对应的编号, 对于每个栅栏, 要开一个 pair, 记录当前栅栏奶牛产奶的结束时间和自己的编号.

代码:

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
47
48
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct cow{
int start;
int end;
int id;
};
int ans[50001];
cow cows[50001];
bool cmp(cow a,cow b){
return a.start<b.start;
}

int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>cows[i].start>>cows[i].end;
cows[i].id = i;
}
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int, int> > > que;
sort(cows,cows+n,cmp);
for(int i=0;i<n;i++){
if(que.empty()||que.top().first>=cows[i].start){
pair<int,int> stall;
stall.first = cows[i].end;
stall.second = (int)que.size();
ans[cows[i].id] = stall.second;
que.push(stall);
}
else{
pair<int,int> stall = que.top();
que.pop();
stall.first = cows[i].end;
ans[cows[i].id] = stall.second;
que.push(stall);
}
}
cout<<que.size()<<endl;
for(int i=0;i<n;i++){
cout<<ans[i]+1<<endl;
}
return 0;
}

纸牌均分问题

直接来看题:

这道题用贪心策略解决, 具体的策略为每次移动都让被移动方达到最终的状态.

在这里, 最终状态是已知的(求和后除以 $N$ 就好), 我们要达到贪心策略, 那就是根据最终状态来算出当前纸牌需要移动或者获得多少张牌才达到最终状态, 例如 9 8 17 6 中, 最终状态为 10, 我们先将每一个数减去 10, 得到 -1 -2 7 -4.然后从左往右开始, 第一个牌堆是-1, 那就把 -1 加到第二个牌堆去, 此时为 0 -3 7 -4, 在到第二个牌堆, 将 -3 移过去, 就变成 0 0 4 -4, 以此类推最后到达状态 0 0 0 0, 并记录移动次数即可.

具体代码有很多细节,减去均值后, 要找到左起第一个非 0 的和右起第一个非 0 的才可以继续, 并且在移牌的时候可能会产生 0 , 或者中间就有为 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
34
35
36
37
38
#include<iostream>
using namespace std;

int main(){
int n;
int avg=0, res=0;
int num[110];
for(int i=0; i<n;i++){
cin>>num[i];
avg+=num[i];
}
avg = avg/n;
for(int i=0; i<n;i++){
num[i] -= avg;
}
int i=0; j=n-1;
// 找到左边起第一个非 0
while(num[i]==0 && i<n){
i++;
}
// 找到右边起第一个非 0
while(num[j]==0 && j>=0){
j--;
}
while(i<j){
num[i+1] += num[i];
num[i] = 0;
res++;
i++;
// 如果移牌后产生了 0
while(num[i]==0 && i<j){
i++;
}
}
cout<<res<<endl;
return 0;
}