贪心算法 - 常见的问题总结(三)

简介: 贪心算法 - 常见的问题总结(三)

什么是贪心

贪心:贪心在解决问题上是目光短浅的,仅仅根据当前的已知信息就做出选择,并且一旦做了选择,就不再更改

常见的贪心问题

  1. 区间问题
  2. Huffman树
  3. 排序不等式
  4. 绝对值不等式
  5. 推公式

排序不等式

排队打水

典型题例:

有 n 个人排队到 1 个水龙头处打水,第 i 个人装满水桶所需的时间是 ti,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?

示例 :

输入:第一行包含两个整数 s 和 t,表示给定线段区间的两个端点。
      第二行包含整数 N,表示给定区间数。
       接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
7
3 6 1 4 2 5 7
输出:
56

思路:左端点排序 + 贪心决策

  1. 先从小到大排序,然后再进行计算
  2. 打水的时间总和为t[1](n1)+t[2](n2)++t[n](nn)=t[i](ni1),下标从零开始

代码:

#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 家商店,它们的坐标分别为A1AN

现在需要在数轴上建立一家货仓,每天清晨,从货仓到每家商店都要运送一车商品。

为了提高效率,求把货仓建在何处,可以使得货仓到每家商店的距离之和最小

示例 :

输入:第一行输入整数 N。
      第二行 N 个整数 A1∼AN。
4
6 2 9 1
输出:
12

思路

中位数最优解

相关题目
  1. 一维扩展到二维:3167 星星还是树
  2. 扩展到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)
#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等技术内容,立即学习

相关文章
|
存储 缓存 算法
409操作系统学习笔记——内存管理(二)
409操作系统学习笔记——内存管理
2551 1
409操作系统学习笔记——内存管理(二)
|
人工智能 算法 安全
详解贪心算法
详解贪心算法
|
9月前
|
数据采集 存储 算法
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
349 0
|
11月前
|
监控 搜索推荐 安全
探究亚马逊详情API接口:开发与应用
在数字化时代,亚马逊作为全球领先的电商平台,为商家和消费者提供了丰富的商品信息和便捷的购物体验。本文深入探讨了亚马逊详情API接口的获取与运用,帮助开发者和商家实时监控商品数据、分析市场趋势、优化价格策略、分析竞争对手、构建推荐系统及自动化营销工具,从而在竞争中占据优势。文章还提供了Python调用示例和注意事项,确保API使用的安全与高效。
348 3
idea 打不开,电脑上下了多个IDEA,新下的IDEA双击打不开,新版IDEA打不开,超实用简单解决办法
一个简单实用的方法来解决新安装的 IntelliJ IDEA 打不开的问题,通常是由于旧版本未卸载干净导致配置文件冲突,建议删除旧版的配置文件来解决这个问题。
3037 1
|
供应链 搜索推荐 数据管理
CDGA|数据治理:解锁各行业数据驱动业务发展的新篇章
数据治理已成为推动各行业业务发展的重要引擎。通过实施科学的数据治理策略,企业能够充分挖掘数据价值,提升运营效率,优化决策过程,实现可持续发展。未来,随着技术的不断进步和数据的持续积累,数据治理将在更多领域发挥重要作用,为企业和社会创造更大价值。
开入开出电路
详细介绍了工控领域的开入开出电路的构成
|
11月前
|
前端开发 JavaScript 中间件
React中使用​​useReducer​​​高阶钩子来管理状态
通过本文的介绍,您可以在React中使用 `useReducer`高阶钩子来管理复杂的状态逻辑。`useReducer`不仅提供了清晰的状态管理方式,还可以通过与 `useContext`结合,实现全局状态管理。此外,通过自定义中间件,可以进一步扩展其功能。希望本文对您理解和应用 `useReducer`有所帮助。
177 0
如何在IDEA中创建Module、以及怎样在IDEA中删除Module?
这篇文章介绍了在IntelliJ IDEA中使用Module的原因、创建Module的步骤以及如何从硬盘上删除Module。
如何在IDEA中创建Module、以及怎样在IDEA中删除Module?
|
网络协议 API PHP
PhalApi:在宝塔一键安装部署PHP开源接口框架的教程
要在宝塔面板上一键安装部署PhalApi开源接口框架,首先进入宝塔软件商店,切换到“一键部署”选项,搜索“phalapi”并点击“一键部署”。安装时需填写接口域名、数据库名及密码,提交后等待安装完成。安装成功后可在宝塔面板中查看新站点和源代码目录,并通过DNS解析设置访问接口域名,如`http://myapi.phalapi.net/`。默认开启的调试模式便于测试,可通过修改`config/sys.php`中的`debug`值为`false`关闭。最后,在源代码中开发自己的PHP接口,PhalApi会自动生成在线接口文档,方便后续调用与维护。更多详细教程可参考官方文档。