算法基础：贪心算法入门 (上) | 极客日志

C++算法

算法基础：贪心算法入门 (上)

贪心算法是一种在每一步选择中都采取当前状态最优解的策略。本文涵盖五个典型例题：货仓选址利用中位数最小化距离；最大子段和通过维护前缀和最大值求解；纪念品分组采用排序后首尾配对策略；排座椅分别统计行列干扰次数并选取最大项；矩阵消除游戏则通过枚举列组合配合贪心选行。文章提供 C++ 代码实现及逻辑证明，适合算法初学者掌握贪心思想。

暖阳发布于 2026/2/70 浏览

算法基础：贪心算法入门 (上)

文章配图

前言

贪心算法是两级分化很严重的算法，简单的题目会觉得理所当然，难的题目怎么想也想不出来。与其说是算法，贪心更多的是一种解题的思想，这种思想得具体问题具体分析，因此千变万化没有模板，我们可能上一个贪心题目会写，下一个就不会写了，并且两个题目之间可能没有明显的共同点。有时候，自己想出来的贪心算法是错误的，因此我们需要证明是否正确，但证明的过程一般比较复杂，在时间充裕的时候可以尝试证明。

简单贪心

1. 货仓选址

题目链接:

P10452 货仓选址 - 洛谷

文章配图

算法原理

贪心思想：将商店的位置由从小到大排序，然后把货仓建在商店位置的中位数。(证明在后面)

因此如果 n 是奇数，货舱建在 v[(n + 1) / 2] 位置处

如果 n 是偶数，货舱建在 v[n / 2] 到 v[n / 2 + 1] 之间均可

实操代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v;
    while (n--) {
        int num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    long long ret = 0;
     ( i = ; i < v.() /  + v.() % ; i++) {
        ret += v[v.() - i - ] - v[i];
    }
    cout << ret;
     ;
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> v(n + 1);
    for (int i = 1; i <= n; i++) {
        long long a;
        cin >> a;
        v[i] = a;
    }
    int right = 1;
    long long ret = -2e9;
    long long prev = 0;
    while (right <= n) {
        if (prev < 0) {
            ret = max(ret, v[right]);
            prev = v[right];
        } else {
            ret = max(ret, prev + v[right]);
            prev += v[right];
        }
        right++;
    }
    cout << ret;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v;
    while (m--) {
        int num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());
    int ret = 0;
    int left = 0;
    int right = v.size() - 1;
    while (left <= right) {
        int sum = v[left];
        if (sum + v[right] <= n) left++;
        ret++;
        right--;
    }
    cout << ret;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
struct node {
    int index;
    int cnt;
} row[N], col[N];
int m, n, k, l, d;
// 按照 cnt 从大到小排序
bool cmp1(node& x, node& y) {
    return x.cnt > y.cnt;
}
// 按照 index 从小到大排序
bool cmp2(node& x, node& y) {
    return x.index < y.index;
}
int main() {
    cin >> m >> n >> k >> l >> d;
    // 初始化结构体数组
    for (int i = 1; i <= m; i++) row[i].index = i;
    for (int i = 1; i <= n; i++) col[i].index = i;
    while (d--) {
        int x, y, p, q;
        cin >> x >> y >> p >> q;
        if (x == p) col[min(y, q)].cnt++;
        else row[min(x, p)].cnt++;
    }
    // 对两个数组按照 cnt 从大到小排序
    sort(row + 1, row + 1 + m, cmp1);
    sort(col + 1, col + 1 + n, cmp1);
    // 对 row 数组，前 k 个元素，按照下标从小到大排序
    sort(row + 1, row + 1 + k, cmp2);
    // 对 col 数组，前 l 个元素，按照下标从小到大排序
    sort(col + 1, col + 1 + l, cmp2);
    for (int i = 1; i <= k; i++) {
        cout << row[i].index << " ";
    }
    cout << endl;
    for (int i = 1; i <= l; i++) {
        cout << col[i].index << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    k = min(k, n + m);
    vector<vector<int>> v(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int num;
            cin >> num;
            v[i][j] = num;
        }
    }
    int ret = 0;
    for (int i = 0; i < (1 << n); i++) {
        int tmp1 = i;
        int count = 0;
        vector<int> bit;
        for (int j = 0; j < n; j++) {
            if ((tmp1 & (1 << j)) != 0) bit.push_back(j);
        }
        if (bit.size() > k) continue;
        auto tmp = v;
        int sum = 0;
        for (int sz = 0; sz < bit.size(); sz++) {
            for (int j = 0; j < m; j++) {
                sum += tmp[bit[sz]][j];
                tmp[bit[sz]][j] = 0;
            }
        }
        if (bit.size() < k) {
            vector<int> y(16, 0);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) y[i] += tmp[j][i];
            }
            sort(y.begin(), y.end());
            auto it = y.rbegin();
            for (int i = 0; i < k - bit.size(); i++) {
                sum += *it;
                it++;
            }
        }
        if (sum > ret) ret = sum;
    }
    cout << ret;
    return 0;
}