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

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

什么是贪心

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

常见的贪心问题

  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]∗(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

思路

中位数最优解

相关题目
  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等技术内容,立即学习

相关文章
|
6天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
7059 17
|
6天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2335 10
|
8天前
|
人工智能 前端开发 API
阿里云Qwen4-Max 大模型详解:定位、特征、能力、适用场景与相对Qwen3-Max差异解析
2026年11月11日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问AI平台Token Plan并接入千问办公、Qoder等入口。该版本聚焦知识理解、世界感知、编程与Agentic四项升级,主打复杂编程、专业办公、前端设计与专业软件操作等真实任务。预览期为11月11日10:00至11月25日24:00,仅支持Token Plan调用,到期后模型标识下线;限时2折、新用户再享5折,最低1折可体验。
|
8天前
|
JSON 前端开发 API
阿里云最新Qwen4-Max大模型介绍:模型定位、特征、能力、适用场景解析
2026 年 11 月 11 日,阿里发布第四代旗舰模型Qwen4-Max预览版,首发千问 AI 平台 Token Plan,并同步接入千问办公、Qoder 等入口。该版本聚焦知识理解、世界感知、编程与 Agentic 四项升级,主打复杂编程、专业办公、前端设计与专业软件操作。预览期至 11 月 25 日 24:00,到期后模型标识下线;限时 2 折、新用户再享 5 折,最低 1 折可体验。
|
4天前
|
传感器 安全 区块链
Windows 电脑运行安卓应用教程:开源工具 ApkStart 双击 APK 即装、独立窗口运行
ApkStart 是一款开源Windows工具,让安卓APP像原生软件一样运行:双击APK即安装、生成真实图标、独立窗口启动、开始菜单可搜索。无需传统模拟器,内置QEMU运行时,支持数据互通、ARM兼容与命令行操作。(239字)
|
21天前
|
Linux 开发工具 iOS开发
Codex保姆级教程(下载+安装+登录+使用,含所有版本,2026最新)
Codex是OpenAI推出的开源AI编程智能体,本地运行,可理解整个代码库,支持自然语言指令改代码、执行命令、跑测试、修Bug,兼容Win/macOS/Linux。(239字)
10222 59
|
4天前
|
人工智能 弹性计算 开发工具
零成本玩各大模型!DeepSeek Harness dsh-our-free-model 插件,13 个厂商模型直接用
总结一下:装这个插件,你不用注册、不用绑卡、不用填一个 Key,就能在 DeepSeek Harness 里用上 DeepSeek V4.1 Flash、Kimi K3 这一批前沿模型,而且是白嫖的、还不限量。三步搞定:下载插件,复制包含 `package.json` 的插件目录路径,在「添加插件」里粘贴路径安装并重启。无论是在阿里云 ECS 上通过命令行部署的 Web 版,还是本地的 Electron 桌面端,都能顺利跑通,快速搭建一套零成本的免费模型使用环境。
1058 1
|
7天前
|
Linux API iOS开发
【DSH】DeepSeek Harness新手保姆教程(下载+安装+配置+使用,2026最新实测)
DeepSeek Harness(dsh)是DeepSeek AI开源的智能体框架,秉持“一切皆插件”理念,支持读文件、改代码、跑命令、处理表格、联网搜索等操作。免费开源,兼容Windows/macOS/Linux,提供桌面端与网页端,可灵活安装插件扩展能力。