什么是贪心
贪心：贪心在解决问题上是目光短浅的，仅仅根据当前的已知信息就做出选择，并且一旦做了选择，就不再更改
常见的贪心问题
- 区间问题
- Huffman树
- 排序不等式
- 绝对值不等式
- 推公式
排序不等式
排队打水
典型题例：
有 n 个人排队到 1 个水龙头处打水，第 i 个人装满水桶所需的时间是 ti，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？
示例 ：
输入：第一行包含两个整数 s 和 t，表示给定线段区间的两个端点。 第二行包含整数 N，表示给定区间数。 接下来 N 行，每行包含两个整数 ai,bi，表示一个区间的两个端点。 7 3 6 1 4 2 5 7 输出： 56
思路:左端点排序 + 贪心决策
- 先从小到大排序，然后再进行计算
- 打水的时间总和为t[1]∗(n−1)+t[2]∗(n−2)+…+t[n]∗(n−n)=t[i]∗(n−i−1),下标从零开始
代码：
#include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 100010; int t[N]; int n; int main() { cin >> n; for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]); sort(t, t + n); LL ans = 0; for (int i = 0; i < n; i ++) ans += t[i] * (n - i - 1); printf("%lld", ans); return 0; }
绝对值不等式
合并果子
典型题例：
在一条数轴上有 N 家商店，它们的坐标分别为A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小
示例 ：
输入：第一行输入整数 N。 第二行 N 个整数 A1∼AN。 4 6 2 9 1 输出： 12
思路
中位数最优解
相关题目
- 一维扩展到二维：3167 星星还是树
- 扩展到d维，需要用到退火算法
方法一 O(nlogn)
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n; int a[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++) scanf("%d", &a[i]); sort(a, a + n); int ans = 0; for (int i = 0; i < n; i ++) ans += abs(a[i] - a[n / 2]); printf("%d", ans); return 0; }
方法二O(nlogn)
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n; int a[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++) scanf("%d", &a[i]); sort(a, a + n); int ans = 0; for (int i = 0; i < n; i ++) ans += a[i] - a[i / 2]; //与abs(a[i] - a[n / 2])等价 printf("%d", ans); return 0; }
方法三 用到nth_element()函数O(n)
- nth_element()函数理解参考std::nth_element
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int n; int a[N]; int main() { scanf("%d", &n); for (int i = 0; i < n; i ++) scanf("%d", &a[i]); sort(a, a + n); nth_element(a, a + n / 2, a + n); // int ans = 0; for (int i = 0; i < n; i ++) ans += abs(a[i] - a[n / 2]); printf("%d", ans); return 0; }
充电站
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
