贪心
狭义的贪心
每一步都做出在当前状态下最好或最优的选择，从而希望最终的结果是最好或最优的算法
广义的贪心
通过分析题目自身的特点和性质，只要发现让求解答案的过程待得到加速的结论，都算广义的贪心
贪心是最符合自然智慧的思想，一般分析门槛不高
理解基本的排序、有序结构，有基本的逻辑思维就能理解
但是贪心的题目，千题千面，极难把握
难度在于证明局部最优可以得到全局最优。不过可以使用对数器验证贪心算法的正确性。
题目 1 最大数
思路：
- 让「拼起来更大的数」排在前面。
- 把每个数转为字符串，按照
a + b > b + a排序后拼接即可。 - 特判一下有多个
0的情况，返回0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<string> vec;
string ans;
string largestNumber(vector<int> &nums) {
for (auto num : nums) {
string str_num = to_string(num);
vec.push_back(str_num);
}
sort(vec.begin(), vec.end(),
[&](string &a, string b) { return a + b > b + a; });
for (auto it : vec) {
ans += it;
}
if (ans[0] == '0') {
return "0";
}
return ans;
}
题目 2 两地调度
思路：
- 先假设所有人都去 A 城市，将价格累加，并求出去 A 城市和 B 城市的差值。
- 然后按照差值从小到大排序，将差值最小的前
n/2个人去 B 城市，将差值最大的后n/2个人去 A 城市。
1
2
3
4
5
6
7
8
9
10
11
12
13
int twoCitySchedCost(vector<vector<int>> &costs) {
int sum = 0;
vector<int> arr(costs.size());
for (int i = 0; i < costs.size(); i++) {
arr[i] = costs[i][1] - costs[i][0];
sum += costs[i][0];
}
sort(arr.begin(), arr.end());
for (int i = 0; i < costs.size() / 2; i++) {
sum += arr[i];
}
return sum;
}
题目 3 吃掉 N 个橘子的最少天数
思路：
- 让
n个橘子尽快的达到 2 或 3 的倍数，并且使用记忆化搜索 dfs双路求解答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unordered_map<int, int> dp; // umap防止溢出，记忆化
int dfs(int n) {
if (n <= 1) {
return 1;
}
if (dp[n]) {
return dp[n];
}
// (n % 2 + (1 + dfs(n / 2))) 尽快让橘子被2整除
// (n % 3 + (1 + dfs(n / 3))) 尽快让橘子被3整除
int ans = min(n % 2 + 1 + dfs(n / 2), n % 3 + 1 + dfs(n / 3));
dp[n] = ans;
return ans;
}
int minDays(int n) { return dfs(n); }
题目 4 最多线段重合问题
思路：
- 把每个区间按左端点排序，顺次扫描，用小根堆维护当前“仍在进行”的区间——堆顶就是最早结束的会议时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n;
vector<pair<int, int>> line;
priority_queue<int, vector<int>, greater<int>> heap;
signed main() {
cin >> n;
line.resize(n);
for (int i = 0; i < n; i++) {
cin >> line[i].first >> line[i].second;
}
sort(line.begin(), line.end(), [&](pair<int, int> a, pair<int, int> b){
return a.first < b.first;
});
int ans = 0;
for (int i = 0; i < n; i++) {
while (heap.size() > 0 && heap.top() <= line[i].first) {
heap.pop();
}
heap.push(line[i].second);
ans = max(ans, (int)heap.size());
}
cout << ans << endl;
}
题目 5 课程表 III
思路：
- 按 ddl 升序扫，能直接上就上；上不了就看看已经选的最耗时的一门课，如果它比当前课还长，就“退掉”它改上当前课——这样总时间被压缩，后面还能再塞别的课。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int scheduleCourse(vector<vector<int>> &courses) {
sort(courses.begin(), courses.end(),
[&](vector<int> &a, vector<int> &b) { return a[1] < b[1]; });
priority_queue<int> heap;
int time = 0;
for (auto c : courses) {
if (time + c[0] <= c[1]) {
heap.push(c[0]);
time += c[0];
} else {
if (!heap.empty() && heap.top() > c[0]) {
time -= heap.top();
heap.pop();
heap.push(c[0]);
time += c[0];
}
}
}
return heap.size();
}
题目 6 合并果子
思路：
- 哈夫曼编码。
- 每次把最小的两堆合并，累加合并费用，直到只剩一堆；累加和就是最小总代价。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n;
priority_queue<int, vector<int>, greater<int>> heap;
void solve() {
int ans = 0;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
heap.push(x);
}
while (heap.size() != 1) {
int x = heap.top();
heap.pop();
int y = heap.top();
heap.pop();
ans += x + y;
heap.push(x + y);
}
cout << ans << endl;
}
