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

贪心算法入门（二）

news 来源：原创 2025/5/9 0:17:03

第1题越野跑查看测评数据信息

为了能在下一次跑步比赛中有好的发挥，桐桐在一条山路上开始了她的训练。桐桐希望能在每次训练中跑得尽可能远，不过她也知道农场中的一条规定：独自进山的时间不得超过M秒(1 <= M <= 10,000,000)。

整条山路被桐桐划分成T个长度相同的小段(1 <= T <= 100,000)，用S_i表示第i个小段的路况。S_i为U，F，D这3个字母之一，它们分别表示第i个小段是上坡、平地，或是下坡。

桐桐要花U秒(1 <= U <= 100)才能跑完一段上坡路，跑完一段平地的耗时是F秒(1 <= F <= 100)，跑完一段下坡路要花D秒(1 <= D <= 100)。注意，沿山路原路返回的时候，原本是上坡路的路段变成了下坡路，原本是下坡路的路段变成了上坡路。

桐桐想知道，在能按时返回农场的前提下，她最多能在这条山路上跑多远。

输入格式

第1行: 5个用空格隔开的整数：M，T，U，F，D。

第2..T+1行: 第i+1行为1个字母S_i，描述了第i段山路的路况。

输出格式

输出1个整数，为桐桐在按时回到农场的前提下，最多能跑到多远。

输入/输出例子1

输入：

13 5 3 2 1

ufudf

输出：

样例解释

【样例说明】

说明:桐桐跑步的最大耗时为13秒（这么短...），她跑步的山路一共被划成5段。桐桐跑完一段上坡路的耗时为3秒，平地为2秒，下坡路为1秒。山路各段的走向如下图所示：

桐桐跑完山路的前3段，然后返回，总耗时为3 + 2 + 3 + 1 + 2 + 1 = 12秒，只比她能在外面呆的时限少1秒。如果她跑得更远，就无法按时回到农场。

#include<bits/stdc++.h>
using namespace std;
int m,t,u,f,d,x,o,i;
string s;
int main(){cin>>m>>t>>u>>f>>d>>s;for(i=0;;i++){if(s[i+1]=='u'||s[i+1]=='d')x=(u+d);else x=f*2;if(o+x>m||i==s.size())break;if(s[i]=='u'||s[i]=='d')o+=(u+d);else o+=f*2;}    cout<<i;return 0;
}

第2题逃生查看测评数据信息

迷宫被分成N行M列的格子。从上往下看，行的编号是1至N。从左往右看，列的编号是1至M。你现在位于第1行第1列格子，迷宫的出口在第N行第M列的格子。每进入一个格子都要消耗能量。迷宫格子的能量有点奇特，同一行格子消耗的能量是相等的，第1行的每一个格子消耗的能量都是E[1]，第2行的每一个格子消耗的能量都是E[2],....第N行的每一个格子消耗的能量都是E[N]。现在你要从左上角格子走到右下角格子，每一步可以从当前格子走到相邻的上、下、左、右四个格子之一，你的目标是消耗最小的总能量。注意：左上角格子和右下角格子消耗的能量也要算。

输入格式

第一行，M和N。（

）

接下来有N个数，第i个是E[i]。

输出格式

一个整数。

输入/输出例子1

输入：

5 6

3 2 5 4 2 8

输出：

样例解释

1<=n<=50,1<=m<=1000000000,1<=e[i]<=1000

#include<bits/stdc++.h>
using namespace std;
long long x,n,s,m,minn=LONG_LONG_MAX;
int main(){cin>>m>>n;for(int i=1;i<=n;i++){cin>>x;s+=x;minn=min(minn,x);}cout<<s+minn*(m-1);return 0;
}

第3题二零二零查看测评数据信息

给出一个字符串S，其中满足S的每一个字符都是数字字符，你要删除S的连续一段字符（也可以删除0个字符），使得剩下的字符依次连接起来的字符串是“2020”,可以做到吗?如果可以做到输出“YES”，否则输出“NO”。

输入格式

第一行，一个整数G，表示有G组测试测试。1<=G<=10。

每组测试格式如下：

第一行，一个整数n，表示字符串S的长度。1<=n<=200。

第二行，字符串S。

输出格式

共G行，每行一个字符串，“YES”或“NO”，双引号不用输出。

输入/输出例子1

输入：

20192020

22019020

2020

20002

729040

输出：

YES

#include<bits/stdc++.h>
using namespace std;
long long m,n,x;
string s;
int main(){cin>>m;for(int i=1;i<=m;i++){cin>>n>>s;if(s[0]=='2'&&s[s.size()-3]=='0'&&s[s.size()-2]=='2'&&s[s.size()-1]=='0')cout<<"YES";else if(s[0]=='2'&&s[1]=='0'&&s[s.size()-2]=='2'&&s[s.size()-1]=='0')cout<<"YES";else if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[s.size()-1]=='0')cout<<"YES";else if(s[s.size()-4]=='2'&&s[s.size()-3]=='0'&&s[s.size()-2]=='2'&&s[s.size()-1]=='0')cout<<"YES";else if(s[0]=='2'&&s[1]=='0'&&s[2]=='2'&&s[3]=='0')cout<<"YES";else cout<<"NO";cout<<'\n';}return 0;
}

第4题学生分组查看测评数据信息

有N组学生，给出初始时每组中的学生个数，再给出每组学生人数的上界R和下界L(L<=R)，每次你可以在某组中选出一个学生把他安排到另外一组中，问最少要多少次才可以使N组学生的人数都在[L,R]中。

输入格式

第一行一个整数N，表示学生组数； n<=100
第二行N个整数，表示每组的学生个数；100
第三行两个整数 L，R，表示下界和上界

输出格式

一个数，表示最少的交换次数，如果不能满足题目条件输出-1

输入/输出例子1

输入：

2
10 20
10 15

输出：

#include<bits/stdc++.h>
using namespace std;
int n,l,r,a[100005],s,h,s1,s2;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s+=a[i];}cin>>l>>r;if(r*n<s||l*n>s){cout<<"-1";return 0;}else{for(int i=1;i<=n;i++){if(l>a[i])s1+=l-a[i];if(r<a[i])s2+=a[i]-r;}}cout<<max(s1,s2);return 0;
}

第5题回文数列查看测评数据信息

czm非常喜欢回文数列。回文数列是指一个包含N个整数的数列A，分别为A[1],A[2],……,A[n]，对于第i(1<=i<=N)个数A[i]，都有A[i]=A[N-i+1]。但是回文数字非常难得到。

现在czm想到了一个办法，他可以将数列中，任意两个相邻的数字合并，用它们的和来代替，合并完成的值还可以和其他值不断合并，直到只剩下一个数。要知道一个数肯定是回文数列。

当然，czm希望他的回文数列尽可能长，因此，请你帮助czm计算一下，对于一个长度为N的数列，经过最少多少次合并，可以构成一个回文数列。

输入格式

第一行一个整数N（1<=N<=500000），表示数列中整数的个数。

第二行包含N个正整数，中间用空格分开，表示数列中的数字。

输出格式

输出一个最小合并次数，使得数列变成回文数列。

输入/输出例子1

输入：

1 2 3

输出：

输入/输出例子2

输入：

5
1 2 4 6 1

输出：

输入/输出例子3

输入：

4
1 4 3 2

输出：

#include<bits/stdc++.h>
using namespace std;
long long n,a[1000005],s;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1,j=n;i<j;){if(a[i]==a[j]){i++;j--;}else if(a[i]>a[j]){a[j-1]+=a[j];j--;s++;}else if(a[i]<a[j]){a[i+1]+=a[i];i++;s++;}}cout<<s;return 0;
}

第6题均分纸牌查看测评数据信息

有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N=4，4 堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6 移动3次可达到目的：从 ③ 取 4 张牌放到 ④ （9 8 13 10） -> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。

输入格式

第一行N。第二行A1 A2 … An （每堆纸牌初始数）

输出格式

所有堆均达到相等时的最少移动次数。（1 <= N <= 100，l<= Ai <=10000 ）

输入/输出例子1

输入：

9 8 17 6

输出：

#include<bits/stdc++.h>
using namespace std;
long long a[100005],n,x,t,s;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];t+=a[i];}x=t/n;for(int i=1;i<=n;i++){a[i]-=x;}for(int i=1;i<n;i++){if(a[i]==0)continue;a[i+1]+=a[i];s++;}cout<<s;return 0;
}

第7题叠罗汉(NHOI2019xx6) 查看测评数据信息

农场的N头奶牛喜欢玩叠罗汉游戏，就是几头奶牛1头奶牛接着1头奶牛的站成一柱子形状。不过奶牛的力量不一样，用数值Ci表示第i头奶牛它的上面最多可以站多少头奶牛，问这些奶牛最少可以站成几个柱子形状。

输入格式

第一行1个整数N，表示有多少头奶牛。1<=N<=1000。

第二行N个正整数Ci，表示这些奶牛的力量。0<=Ci<=1000。

输出格式

一个整数，表示最少成几个“罗汉”。

输入/输出例子1

输入：

0 2 1 2 2

输出：

样例解释

可以第1、第3、第2头奶牛从上向下叠罗汉；

第4、第5头奶牛叠罗汉。

#include<bits/stdc++.h>
using namespace std;
int n,a[1005],s,k,x;
int main(){cin>>n;for(int i=1;i<=n;i++){int t;cin>>t;a[t]++;}while(n>k){x=0,s++;for(int i=0;i<1000;){if(i>=x&&a[i]!=0)a[i]--,k++,x++;else i++;}}cout<<s;return 0;
}

第8题放书(noip2008mn) 查看测评数据信息

作为一名图书管理员，每天结束时你要把书放回书架。书架和堆放书的地方可以认为在一个X轴上，堆书的地点坐标为0，书架的位置在正、负整数点上。你开始的位置就在0点，你一次最多可以拿N本书，问你最少要走多少路程才可以把书全部放回各自的书架上。

输入格式

第一行有两个整数K和N， 1<=K,N <=50，分别代表书本总数和你一次最多可拿的书本数。后面有K个整数(在-10000到10000之间)，分别表示每本书所要放回书架的位置。

输出格式

最少需要的路程。注：你最后可以停在任意的位置，不必返回到开始位置。

输入/输出例子1

输入：

7 2

-37 2 -6 -39 -29 11 -28

输出：

131

输入/输出例子2

输入：

8 3

-18 -9 -4 50 22 -26 40 -45

输出：

158

#include<bits/stdc++.h>
using namespace std;
template<typename T>
T max(T&a,T&b){return a<b?b:a;
}
int k,n,s,i,j;
int main(){cin>>k>>n;vector<int>v(k);for(int i=0;i<k;i++){cin>>v[i];}sort(v.begin(),v.end());for(i=0;v[i]<=0;i++);for(j=0;j<i;j++){if(j%n==0)s-=v[j]*2;}for(int j=v.size();j>i;j--){if((v.size()-j)%n==0){s+=v[j-1]*2;}}s-=max(-v.front(),v.back());cout<<s;return 0;
}

贪心算法入门（二）

第1题越野跑查看测评数据信息为了能在下一次跑步比赛中有好的发挥，桐桐在一条山路上开始了她的训练。桐桐希望能在每次训练中跑得尽可能远，不过她也知道农场中的一条规定：独自进山的时间不得超过M秒(1 < M < 10,000,000)。整条…...

编程日记 2025/5/9 0:17:03

欧拉函数——acwing

题目一：欧拉函数 873. 欧拉函数 - AcWing题库分析（欧拉函数相关知识点） 互质数不了解可以参考之前笔记，以便更好了解： 数论—快速幂，欧几里得及其扩展，逆元，单位元_数论单位元函…...

编程日记 2025/5/5 1:25:52

Spring集成Mybatis的实现

实现步骤大纲第一步：准备数据库表使用t_act表（账户表） 第二步：IDEA中创建一个模块，并引入依赖 spring-contextspring-jdbcmysql驱动mybatismybatis-spring：mybatis提供的与spring框架集成的依赖德鲁伊连…...

编程日记 2025/5/9 6:04:48

Redis中的分布式锁（步步为营）

分布式锁概述分布式锁指的是，所有服务中的所有线程都去获取同一把锁，但只有一个线程可以成功的获得锁，其他没有获得锁的线程必须全部等待，直到持有锁的线程释放锁。分布式锁是可以跨越多个实例，多个进程的锁分布…...

编程日记 2025/5/1 9:48:42

Linux下的三种 IO 复用

目录一、Select 1、函数 API 2、使用限制 3、使用 Demo 二、Poll 三、epoll 0、实现原理 1、函数 API 2、简单代码模板 3、LT/ET 使用过程 （1）LT 水平触发 （2）ET边沿触发 4、使用 Demo 四、参考链接一、Select 在…...

编程日记 2025/5/5 6:34:35

微服务即时通讯系统的实现（服务端）----（2）

目录 1. 语音识别子服务的实现1.1 功能设计1.2 模块划分1.3 模块功能示意图1.4 接口的实现 2. 文件存储子服务的实现2.1 功能设计2.2 模块划分2.3 模块功能示意图2.4 接口的实现 3. 用户管理子服务的实现3.1 功能设计3.2 模块划分3.3 功能模块示意图3.4 数据管理3.4.1 关系数据…...

编程日记 2025/4/29 17:39:06

数据库原理-期末复习基础知识第二弹

1、数据的逻辑独立性是指外模式/模式映像当模式改变的时候，由数据库管理员对各个外模式/模式的映像做出相应改变，使外模式保持不变。由于应用程序是按照外模式进行编写的，故应用程序不必修改，保证了数据与程序的逻辑独立性。 …...

编程日记 2025/5/5 17:27:10

智能云在线编辑网站（完结篇）

开始及初步计划 1.前端tiptip编辑器框架vue3 2.后端Pythonflaskmysql 3.大模型调用：飞桨系列（ppasr） 前言：以此篇谨记从软件杯到天津生成式ai答辩过程及结束。『如蚍蜉见青天，双肩难挑日月』，感叹世事多…...

编程日记 2025/5/4 9:25:48

多源传感器构建机器人的Gazebo模型

构建包含GNSS、IMU、LiDAR、Camera传感器的Gazebo模型涉及多个步骤，包括设置工作环境、创建URDF文件、安装必要的Gazebo插件和依赖项。以下是一个详细的步骤指南，帮助你开始构建这个Gazebo模型。 1. 设置工作环境首先，确保你已经安装了ROS…...

编程日记 2025/4/28 12:32:41

linux中top 命令返回数据解释

当您在 Linux 终端中运行 top 命令时，它会显示一个动态更新的系统状态视图，其中包括许多有关系统性能的数据。下面是对 top 命令返回数据的详细解释：标题栏 top - 22:46:12 up 2 days, 3:14, 1 user, load average: 0.05, 0.07, 0.09 22:46:12：当前时间。up 2 days, 3:14…...

编程日记 2025/5/9 5:59:09

【Vue3】【Naive UI】＜NDropdown＞标签

【Vue3】【Naive UI】标签基本设置自定义渲染交互事件其他属性【VUE3】【Naive UI】＜NCard＞ 标签【VUE3】【Naive UI】＜n-button＞ 标签【VUE3】【Naive UI】＜a＞ 标签【VUE3】【Naive UI】&#xff1c…...

编程日记 2025/5/9 6:00:31

ADS学习笔记 7. 超外差接收机设计

基于ADS2023 update2 更多ADS学习笔记：ADS学习笔记 1. 功率放大器设计ADS学习笔记 2. 低噪声放大器设计ADS学习笔记 3. 功分器设计ADS学习笔记 4. 微带分支定向耦合器设计ADS学习笔记 5. 微带天线设计ADS学习笔记 6. 射频发射机设计目录 -1、射频接收机性能指标…...

编程日记 2025/5/4 7:40:20

新型大语言模型的预训练与后训练范式，阿里Qwen

前言：大型语言模型（LLMs）的发展历程可以说是非常长，从早期的GPT模型一路走到了今天这些复杂的、公开权重的大型语言模型。最初，LLM的训练过程只关注预训练，但后来逐步扩展到了包括预训练和后训练在内的完整…...

编程日记 2025/5/7 4:54:41

k8s 1.28 二进制安装与部署

第一步 ：配置Linux服务器 #借助梯子工具 192.168.196.100 1C8G kube-apiserver、kube-controller-manager、kube-scheduler、etcd、kubectl、haproxy、keepalived 192.168.196.101 1C8G kube-apiserver、kube-controller-manager、kube-scheduler、etcd、kubectl、…...

编程日记 2025/5/4 10:35:24

Ubuntu 常用解压与压缩命令

.zip文件 unzip FileName.zip # 解压 zip DirName.zip DirName # 将DirName本身压缩 zip -r DirName.zip DirName # 压缩，递归处理，将指定目录下的所有文件和子目录一起压缩 zip DirName.zip DirName 行为： 只压缩 DirName 目录本身&#xff…...

编程日记 2025/5/9 5:52:58

使用ECharts创建带百分比标注的环形图

在数据可视化领域，环形图是一种非常有效的图表类型，它能够清晰地展示各部分与整体的关系。今天，我们将通过ECharts来创建一个带百分比标注的环形图，并详细解释如何实现这一效果。 1. 数据准备首先，我们定义了一些基础…...

编程日记 2025/5/4 12:10:11

lvs虚拟服务器之LVS-NAT模式

一.集群二.LVS:虚拟服务器:工作在传输层,解决高并发三.LVS-NAT一.集群1.概念:集群就是一组计算机集群核心：任务调度集群目的提高性能,降低成本,提高可扩展性,增强可靠性集群分类HA：高可用集群（High Availability Cluster）:避免单…...

编程日记 2025/5/4 2:12:22

虚拟机添加硬盘驱动,Windows 系统添加 VirtIO 驱动（Windows ISO 安装镜像添加驱动）

为什么要在 ISO 镜像里添加驱动？而不是在进系统以后装驱动？一切都是形势所迫。如果你也是爱折腾的人，那么这也会成为一个有用的方案之一。　　最近，因为在给公司研究部署 OpenStack，在制作初始镜像（也就是…...

编程日记 2025/5/6 8:22:16

20241128解决Ubuntu20.04安装libesd0-dev异常的问题

20241128解决Ubuntu20.04安装libesd0-dev异常的问题 2024/11/28 16:36 缘起：中科创达的高通CM6125开发板的Android10的编译环境需要。安装异常：rootrootrootroot-X99-Turbo:~$ rootrootrootroot-X99-Turbo:~$ sudo apt-get install libesd0-dev Readi…...

编程日记 2025/5/9 6:01:54

Linux命令进阶·如何切换root以及回退、sudo命令、用户/用户组管理，以及解决创建用户不显示问题和Ubuntu不显示用户名只显示“$“符号问题

目录 1. root用户（超级管理员） 1.1 用于账户切换的系统命令——su 1.2 退回上一个用户命令——exit 1.3 普通命令临时授权root身份执行——sudo 1.3.1 为普通用户配置sudo认证 2. 用户/用户组管理 2.1 用户组管理 2.2 用户管理 2.2.1 …...

编程日记 2025/5/7 15:05:12

基于链表的基础笔试/面试题

1. 反转链表问题描述：反转一个单向链表。示例： 输入：1 → 2 → 3 → 4 → 5 输出：5 → 4 → 3 → 2 → 1 class ListNode {int val;ListNode next;ListNode(int x) {val x;} }public class LinkedList {public ListNode …...

编程日记 2025/5/1 22:33:01

文件比较和文件流

文件比较和文件流一、文本比较工具 diff1.基本用法1.1输出格式 2.常用选项二、文件流1.文件的打开模式2.文件流的分类ifstreamofstreamfstrem区别 3.文件流的函数1. 构造函数2. is_open 用于判断文件是否打开3. open4. getline5. close6. get()7. read8. write9. put10. gcou…...

编程日记 2025/5/6 14:59:59

unity如何让一个物体拥有按钮功能

在 Unity 中，要让一个物体（例如一个 3D 模型、UI 元素或其他对象）变成一个按钮，你需要为它添加交互功能。这通常意味着让物体能够响应点击事件，像 UI 按钮那样触发某些行为。对于 3D 物体，可以通过射线检测…...

编程日记 2025/5/3 10:07:23

【RISC-V CPU Debug 专栏 1 -- RISC-V debug 规范】

文章目录 RISC-V Debug调试用例支持的功能限制和不包括的内容RISC-V 调试架构的主要组件用户与调试主机调试翻译器调试传输硬件调试传输模块（DTM）调试模块（DM）调试功能触发模块版本介绍RISC-V Debug RISC-V 调试规范为 RISC-V 处理器提供了一套标准化的调试接口和功能，旨…...

编程日记 2025/4/23 7:26:13

【论文阅读】Federated learning backdoor attack detection with persistence diagram

目的：检测联邦学习环境下，上传上来的模型是不是恶意的。 1、将一个模型转换为|L|个PD,（其中|L|为层数） 如何将每一层转换成一个PD？ 为了评估第𝑗层的激活值，我们需要𝑐个输入来获…...

编程日记 2025/5/5 10:41:09

IDEA Maven 打包找不到程序包错误或找不到符号,报错“程序包不存在“

参考文章：https://blog.csdn.net/yueeryuanyi/article/details/14211090 问题：IDEA Maven 打包找不到程序包错误或找不到符号,报错“程序包不存在“编译都没问题解决思路 – >【清除缓存】 1. 强制刷新Maven缓存选择 Maven 标签，Exe…...

编程日记 2025/5/6 22:37:46

MySQL数据库做题笔记

题目链接https://leetcode.cn/problems/invalid-tweets-ii/description/https://leetcode.cn/problems/invalid-tweets-ii/description/ # Write your MySQL query statement below SELECT tweet_id FROM Tweets where LENGTH(content)>140 OR (length(content)-length(rep…...

编程日记 2025/5/3 11:58:04

输入格式

输出格式

输入/输出例子1

样例解释

输入格式

输出格式

输入/输出例子1

样例解释

输入格式

输出格式

输入/输出例子1

输入格式

输出格式

输入/输出例子1

输入格式

输出格式

输入/输出例子1

输入/输出例子2

输入/输出例子3

输入格式

输出格式

输入/输出例子1

输入格式

输出格式

输入/输出例子1

样例解释

输入格式

输出格式

输入/输出例子1

输入/输出例子2

相关文章：