文章

贪心1

贪心算法通过每步选择局部最优解，期望最终达到全局最优，适用于最优化和排序问题。

发表于 更新于
作者 Sylvan
9 分钟阅读
贪心1

贪心1

179. 最大数

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 暴力方法生成所有可能的排列，其中选出字典序最小的结果
    string way1(vector<string> &strs) {
        vector<string> res;
        fc(strs, 0, res);
        sort(res.begin(), res.end());
        return res[0];
    }

    // 全排列
    void fc(vector<string> &strs, int i, vector<string> &res) {
        if (i == strs.size()) {
            string path;
            for (const string &s: strs)
                path += s;
            res.push_back(path);
        } else {
            for (int j = i; j < strs.size(); j++) {
                swap(strs[i], strs[j]);
                fc(strs, i + 1, res);
                swap(strs[i], strs[j]);
            }
        }
    }

    // 正式方法，时间复杂度 O(n*logn)
    string way2(vector<string> &strs) {
        sort(strs.begin(), strs.end(), [](const string &a, const string &b) {
            return (a + b) < (b + a);
        });
        string path;
        for (const string &s: strs)
            path += s;
        return path;
    }

    // 生成长度 1~n 的随机字符串数组
    vector<string> randomStringArray(int n, int m, int v) {
        vector<string> res(rand() % n + 1);
        for (int i = 0; i < res.size(); i++)
            res[i] = randomString(m, v);
        return res;
    }

    // 生成长度 1~m，字符种类有 v 种，随机字符串
    string randomString(int m, int v) {
        int len = rand() % m + 1;
        string res(len, ' ');
        for (int i = 0; i < len; i++)
            res[i] = 'a' + rand() % v;
        return res;
    }

    // 最大数
    string largestNumber(vector<int> &nums) {
        int n = nums.size();
        vector<string> strs(n);
        for (int i = 0; i < n; i++)
            strs[i] = to_string(nums[i]);
        sort(strs.begin(), strs.end(), [](const string &a, const string &b) {
            return (b + a) < (a + b);
        });
        if (strs[0] == "0") return "0";
        string path;
        for (const string &s: strs)
            path += s;
        return path;
    }
};

int main() {
    Solution sol;

    int n = 8; // 数组中最多几个字符串
    int m = 5; // 字符串长度最大多长
    int v = 4; // 字符的种类有几种
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for (int i = 1; i <= testTimes; i++) {
        vector<string> strs = sol.randomStringArray(n, m, v);
        string res1 = sol.way1(strs);
        string res2 = sol.way2(strs);
        if (res1 != res2) {
            cout << "出错了！" << endl;
        }
        if (i % 100 == 0) {
            cout << "测试到第" << i << "组" << endl;
        }
    }
    cout << "测试结束" << endl;
}

1029. 两地调度

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 <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>> &costs) {
        int n = costs.size();
        // <在原数组中的下标，差值>
        vector<pair<int, int>> arr(n);
        for (int i = 0; i < n; ++i)
            arr[i] = make_pair(i, costs[i][1] - costs[i][0]);
        // 根据差值递增排序，差值表示从 a 换到 b 的代价
        sort(begin(arr), end(arr),
             [](const pair<int, int> &p1, const pair<int, int> &p2) { return p1.second < p2.second; });
        int res = 0;
        // 前一半的人去 b
        for (int i = 0; i < n; ++i) {
            res += (i < n / 2) ? costs[arr[i].first][1] : costs[arr[i].first][0];
        }
        return res;
    }
};

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 <vector>
#include <string>
#include <algorithm>

using namespace std;

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>> &costs) {
        int n = costs.size();
        int sum = 0;
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            arr[i] = costs[i][1] - costs[i][0];
            // 假设全都去 a
            sum += costs[i][0];
        }
        sort(begin(arr), end(arr),
             [](const int &p1, const int &p2) { return p1 < p2; });
        // 前一半的人从 a 去 b
        for (int i = 0; i < n / 2; ++i)
            sum += arr[i];
        return sum;
    }
};

1553. 吃掉 N 个橘子的最少天数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    unordered_map<int, int> dp;

    int minDays(int n) {
        if (n <= 1) return n;
        if (dp.find(n) != dp.end()) return dp[n];
        // 能按比例吃就按比例吃，每天吃一个只是为了更快的到达能按比例吃
        int res = min(n % 2 + 1 + minDays(n / 2), n % 3 + 1 + minDays(n / 3));
        dp[n] = res;
        return res;
    }
};

线段重合

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

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

int fc(vector<vector<int>> &lines) {
    int n = lines.size();
    // 根据线段的左端点排序
    sort(begin(lines), end(lines),
         [](const vector<int> &v1, const vector<int> &v2) { return v1[0] < v2[0]; });
    // 小顶堆，根据线段的右端点排序
    priority_queue<int, vector<int>, greater<int>> heap;

    int res = 0;
    // 任何一个重合的区域，一定有一个左端点最大的，下面的循环就是考虑这个最大的左端点是谁
    // [                   ]
    //      [        ]
    //         [        ]
    //      最大的左端点
    for (int i = 0; i < n; ++i) {
        // 堆中保存着的线段的右端点比当前线段的左端点还小
        // 说明没有重合的地方，也不会与后续的线段重合，全部弹出
        while (!heap.empty() && heap.top() <= lines[i][0])
            heap.pop();
        heap.emplace(lines[i][1]);
        res = max(res, (int) heap.size());
    }

    return res;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int>> lines(n, vector<int>(2, 0));
    for (int i = 0; i < n; ++i)
        cin >> lines[i][0] >> lines[i][1];

    cout << fc(lines) << endl;
}

630. 课程表 III

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

#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    int scheduleCourse(vector<vector<int>> &courses) {
        // 按照每门课程的截止时间从小到大排序（更早截止的课程排前面）
        sort(courses.begin(), courses.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[1] < b[1];
        });

        // 创建一个大根堆（优先队列），用于记录已选课程的耗时
        // 堆顶是当前已选课程中耗时最长的那一门
        priority_queue<int> heap;

        // 记录当前来到的时间点
        int time = 0;

        for (const auto &c: courses) {
            int duration = c[0]; // 课程耗时
            int lastDay = c[1];  // 课程必须在这天前完成

            if (time + duration <= lastDay) {
                // 如果加上这门课程不会超过它的截止日期，就选它
                heap.push(duration);
                time += duration;
            } else {
                // 否则，看当前堆中有没有耗时更大的课程可以换掉
                if (!heap.empty() && heap.top() > duration) {
                    time += duration - heap.top();
                    heap.pop();
                    heap.push(duration);
                }
                // 如果当前课程比堆顶课程耗时还大，就直接跳过（因为会更糟）
            }
        }

        // 返回最终能上的课程数，也就是堆的大小
        return heap.size();
    }
};

P1090 [NOIP 2004 提高组] 合并果子

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

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 哈夫曼树的构造过程
int fc(vector<int> &arr) {
    // 小根堆
    priority_queue<int, vector<int>, greater<>> heap(arr.begin(), arr.end());

    int res = 0;
    // 每次弹出两个最小的进行合并，再放回合并后的结果
    while (heap.size() > 1) {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        int merged = a + b;
        res += merged;
        heap.push(merged);
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    cout << fc(arr) << endl;
}
algorithm, problems
Algorithm Greedy
本文由作者按照 CC BY 4.0 进行授权