当前位置: 首页 > news >正文

贪心算法(常见贪心模型)

常见贪心模型

 简单排序模型

最小化战斗力差距

题目分析:

 

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];int main()
{// 请在此输入您的代码cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int disparity = 1e9-1;for (int i = 1;i < n;i++) disparity = min(disparity,a[i+1] - a[i]);cout << disparity << '\n';return 0;
}

 货仓选址 

可以发现,仓库建在中间,可以使得货仓到每家商店的距离之和最小

#include <bits/stdc++.h>
using namespace std;const int N = 100010;int n;
int a[N];int main()
{cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int store = a[n/2 + 1];int res = 0;for (int i = 1;i <= n;i++) {if (i == n/2 + 1) continue;res += abs(store - a[i]);}cout << res << '\n';return 0;
}

总操作一定的情况下的最小代价模型

谈判

如果每次选择代价最小的两个部落合并,不仅可以使得当前代价最小,还可以使得后续合并的代价也尽可能小

局部最优 ==》全局最优

 用数组模拟(O(n^2 log n))

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n;
int a[N];int main()
{// 先排序 找到两个人数最少的部落cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int sum = 0;for (int i = 2;i <= n;i++) {a[i] = a[i] + a[i-1];sum += a[i];sort(a+i,a+1+n);}cout << sum << '\n';return 0;
}

 用优先级队列实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;priority_queue<ll,vector<ll>,greater<ll>> pq;int main()
{//用优先队列实现 每次取其中两个代价最小的部落进行合并,总花费最小int n;cin >> n;for (int i = 1;i <= n;i++){ll x;cin >> x;pq.push(x);}  ll ans = 0;while (pq.size() > 1){ll x = pq.top();pq.pop();ll y = pq.top();pq.pop();ans += x+y;pq.push(x+y);}cout << ans << '\n';return 0;
}
 糖果传递

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1000010;int n;
int a[N];
ll c[N];int main()
{cin >> n;ll sum = 0;for (int i = 1;i <= n;i++) cin >> a[i],sum += a[i];int avg = sum / n;for (int i = n;i > 0;i--) c[i] = c[i+1] + avg - a[i];c[1] = 0;sort(c+1,c+1+n);ll res = 0;for (int i = 1;i <= n;i++) res += abs(c[i] - c[(n+1)/2]);cout << res << '\n';return 0;
}

最少数量的贪心模型

纪念品分组

 

 

 

为了让组数最少,我们要尽可能将两个纪念品打包成一组

怎样的两个纪念品最有可能打包成一组呢,无疑是一个大和一个小的

所以我们先去找最大和最小的,如果不能打包,则去找次小的,直到能打包成一组

不能打包的大的纪念品则单独一组

#include <bits/stdc++.h>
using namespace std;const int N = 30010;int w,n;
int a[N];int main()
{// 请在此输入您的代码cin >> w >> n;int cnt = 0;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);for (int i = 1,j = n;;){if (i > j) break;if (a[i] + a[j] <= w){cnt++;i++,j--;}else {j--;cnt++;}}cout << cnt << '\n';return 0;
}

找规律的贪心模型

分糖果

我们要去使得所有糖果组成的字符串中字典序最大的字符串尽可能小

字符串字典集大小先看首字母大小,其次看后面的字母大小

a < b < c ...

a < aabs...

先给字符串排序,然后分为三类讨论

1️⃣字符串全相等(假设全a),那就尽量使得每个人分到的字符串的最大长度尽可能小,即平分字符串

2️⃣s[x] == s[1] 说明第x个是最小的字符,让它带着后面所有的字符一起输出即可

3️⃣ s[x] != s[1] ,后面一坨字符直接丢到s[1]后面,分给 第一个同学即可

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;int n,x;
char s[N];int main()
{// 请在此输入您的代码cin >> n >> x;cin >> s+1;sort(s+1,s+1+n);if (s[1] == s[n]) {for (int i = 1;i <= n / x + (n % x ? 1 : 0);i++) cout << s[i];}else if (s[1] == s[x]) {for (int i = x;i <= n;i++) cout << s[i];}else {cout << s[x];}return 0;
}
股票买卖II

容易发现规律,如果后一天的股票比当天高,那么就今天买入后一天卖出

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];int main() {cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];int res = 0;for (int i = 1;i <= n;i++){if (a[i] < a[i+1]) res += a[i+1] - a[i];}cout << res << '\n';return 0;
}
乘积最大

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e5 + 10,mod = 1000000009;int n,k;
int a[N];int main()
{cin >> n >> k;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int res = 1;int l = 1,r = n;int sign = 1;if (k % 2) {res = a[r--];k--;if (res < 0) sign = -1;}while (k){ll x = (ll)a[l] * a[l+1],y = (ll)a[r] * a[r-1];if (x * sign > y * sign){res = x % mod * res % mod;l += 2;}else {res = y % mod * res % mod;r -= 2;}k -= 2;}cout << res << endl;return 0;
}

相关文章:

贪心算法(常见贪心模型)

常见贪心模型 简单排序模型 最小化战斗力差距 题目分析&#xff1a; #include <bits/stdc.h> using namespace std;const int N 1e5 10;int n; int a[N];int main() {// 请在此输入您的代码cin >> n;for (int i 1;i < n;i) cin >> a[i];sort(a1,a1n);…...

git自动压缩提交的脚本

可以将当前未提交的代码自动执行 git addgit commitgit squash Git 命令安装指南 1. 创建脚本目录 如果目录不存在&#xff0c;创建它&#xff1a; mkdir -p ~/.local/bin2. 创建脚本文件 vim ~/.local/bin/git-squash将完整的脚本代码复制到此文件中。 3. 设置脚本权限…...

Kinova在开源家庭服务机器人TidyBot++研究里大展身手

在科技日新月异的今天&#xff0c;机器人技术在家庭场景中的应用逐渐成为现实&#xff0c;改变着我们的生活方式。今天&#xff0c;我们将深入探讨一篇关于家用机器人研究的论文&#xff0c;剖析其中的创新成果&#xff0c; 论文引用链接&#xff1a;http://tidybot2.github.i…...

使用 Spring Boot 实现文件上传:从配置文件中动态读取上传路径

使用 Spring Boot 实现文件上传&#xff1a;从配置文件中动态读取上传路径 一、前言二、文件上传的基本概念三、环境准备1. 引入依赖2. 配置文件设置application.yml 配置示例&#xff1a;application.properties 配置示例&#xff1a; 四、编写文件上传功能代码1. 控制器类2. …...

《鸿蒙HarmonyOS应用开发从入门到精通(第2版)》学习笔记——HarmonyOS技术理念

1.2 技术理念 在万物智联时代重要机遇期&#xff0c;HarmonyOS结合移动生态发展的趋势&#xff0c;提出了三大技术理念&#xff08;如下图3-1所示&#xff09;&#xff1a;一次开发&#xff0c;多端部署&#xff1b;可分可合&#xff0c;自由流转&#xff1b;统一生态&#xf…...

将多个 k8s yaml 配置文件合并为一个文件

如下bash脚本实现功能 “将多个k8s的yaml 配置文件” 合并为一个 yaml&#xff0c;使用 --- 分割文件配置。 创建文件 merge_yaml.sh &#xff0c;内容如下&#xff1a; #!/bin/bash# 默认参数 input_patterns() # 匹配的文件模式数组 output_file"combined.yaml"…...

Linux 文件的特殊权限—Sticky Bit(SBIT)权限

本文为Ubuntu Linux操作系统- 第十九期~~ 其他特殊权限: 【SUID 权限】和【SGID 权限】 更多Linux 相关内容请点击&#x1f449;【Linux专栏】~ 主页&#xff1a;【练小杰的CSDN】 文章目录 Sticky&#xff08;SBIT&#xff09;权限基本概念Sticky Bit 的表示方式举例 设置和取…...

MIPI D-PHY/C-PHY/M-PHY 高速串行接口标准

MIPI D-PHY、C-PHY和M-PHY都是MIPI联盟制定的高速串行接口标准。它们都具有低功耗、高速传输速率等特点&#xff0c;但各有侧重&#xff1a; ➢MIPI D-PHY&#xff1a;适用于手机与其他设备之间的数据传输。 ➢MIPI C-PHY&#xff1a;专为手机摄像头而设计。 ➢MIPI M-PHY&am…...

USB免驱IC读写器QT小程序开发

USB免驱全协议IC卡读写器QT小程序开发&#xff0c;读取15693卡。 QT小程序UI开发界面&#xff1a; QT程序代码mainWindow.cpp代码如下&#xff1a; MainWindow::MainWindow(QWidget *parent): QMainWindow(parent), ui(new Ui::MainWindow) {ui->setupUi(this); }MainWind…...

OSCP靶场训练冒险之kioprix4:shell逃逸以及利用数据库提权

声明&#xff01; 学习资源来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…...

NIPS2014 | GAN: 生成对抗网络

Generative Adversarial Nets 摘要-Abstract引言-Introduction相关工作-Related Work对抗网络-Adversarial Nets理论结果-Theoretical Results实验-Experiments优势和不足-Advantages and disadvantages缺点优点 结论及未来工作-Conclusions and future work研究总结未来研究方…...

Postman接口测试01|接口测试基础概念、http协议、RESTful风格、接口文档

目录 一、接口测试基础概念 1、什么是接口 2、接口的类型 3、什么是接口测试 4、为什么要做接口测试 5、接口测试的实现方式 6、什么是自动化接口测试&#xff1f; 二、接口返回的数据格式 1、三种格式 2、Json 三、接口协议 1、webservice协议 2、dubbo协议 3、…...

Linux系统编程——详解页表

目录 一、前言 二、深入理解页表 三、页表的实际组成 四、总结&#xff1a; 一、前言 页表是我们之前在讲到程序地址空间的时候说到的&#xff0c;它是物理内存到进程程序地址空间的一个桥梁&#xff0c;通过它物理内存的数据和代码才能映射到进程的程序地址空间中&#xff…...

SpringBoot + HttpSession 自定义生成sessionId

SpringBoot HttpSession 自定义生成sessionId 业务场景实现方案 业务场景 最近在做用户登录过程中&#xff0c;由于默认ID是通过UUID创建的&#xff0c;缺乏足够的安全性&#xff0c;决定要自定义生成 sessionId。 实现方案 正常的获取session方法如下&#xff1a; HttpSe…...

循环对称复高斯分布(Circularly Symmetric Complex Gaussian Distribution)

一、引言 循环对称复高斯分布&#xff08;Circularly Symmetric Complex Gaussian Distribution&#xff0c;简称CSCG&#xff09;在无线通信、信号处理等领域具有广泛的应用。作为一种特殊的复高斯分布&#xff0c;CSCG具有独特的性质&#xff0c;如循环对称性、高斯性等&…...

xinput1_3.dll放在哪里?当xinput1_3.dll丢失时的应对策略:详细解决方法汇总

在计算机系统的运行过程中&#xff0c;我们偶尔会遇到一些令人困扰的问题&#xff0c;其中xinput1_3.dll文件丢失就是较为常见的一种情况。这个看似不起眼的动态链接库文件&#xff0c;实则在许多软件和游戏的正常运行中发挥着至关重要的作用。一旦它丢失&#xff0c;可能会导致…...

基于STM32的智能家居环境监控系统设计

目录 引言系统设计 硬件设计软件设计系统功能模块 环境监控模块控制模块显示模块系统实现 硬件实现软件实现系统调试与优化结论与展望 1. 引言 随着智能家居技术的发展&#xff0c;环境监控系统已经成为家居管理的重要组成部分。智能家居环境监控系统通过实时监测室内温度、湿…...

Vscode + gdbserver远程调试开发板指南:

本章目录 步骤环境准备网络配置vscode配置步骤 (全图示例)开发板配置开始调试注意: 每次断开之后&#xff0c;开发板都需要重新启动gdbserver才可调试。 参考链接: 步骤 环境准备 将交叉编译链路径加入$PATH变量&#xff1a;确保系统能够找到所需的工具。 export PATH$PATH:/p…...

大表:适用于结构化数据的分布式存储系统

大家觉得有意义和帮助记得及时关注和点赞!!! 译者序摘要1 引言2 数据模型 2.1 行&#xff08;Row&#xff09;2.2 Column Families&#xff08;列族&#xff09; 2.2.1 设计2.2.2 column key 的格式&#xff1a;family:qualifier2.2.3 访问控制和磁盘/内存记账&#xff08;acco…...

深入解析MVCC中Undo Log版本底层存储读取逻辑

一、引言 多版本并发控制&#xff08;MVCC&#xff0c;Multi-Version Concurrency Control&#xff09;是一种广泛应用于关系数据库管理系统中的并发控制技术。它通过保存数据的历史版本&#xff0c;使得在事务并发执行时&#xff0c;每个事务都能看到数据的一致性视图。在MVC…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...