15. 卡牌游戏
目录
题目
思路
C++整体代码(含详细注释)
题目
Description
小张在玩一种卡牌游戏,牌组由张牌组成,其中张上写有数字各一张,其余张上全部是数字。
现在牌组经过随机打乱后,小张拿走其中张牌作为手牌,其余张牌作为牌堆。
小张想经过若干次如下操作使得牌堆自顶向下的牌依次为。
每一次操作,小张选择任意一张手牌放到牌堆底,并将牌堆顶的牌放入手牌。
他想知道最少进行几次操作,使得牌堆自顶向下的牌依次为。
Input
第一行一个数。
第二行个数,表示小张手中的牌。
第三行个数,表示牌堆,数组从左向右的顺序表示牌堆自顶向下的顺序。
Output
一个整数,表示最少执行的操作数
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
| 测试用例 2 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M | 0 |
思路
手上的牌不重要,重要的是牌堆里非0数字的位置,有三种情况:
1)牌堆最后存在1开头连续的数并且其他的数字均符合位置条件
2)牌堆最后存在1开头连续的数但其他的数字不均符合位置条件
3)牌堆最后不存在1开头连续的数
操作方法
- 情况1的操作方式一目了然,直接把1前面的数字挤掉的同时在牌堆尾部添加相应的数字。
结果=1的位置-牌堆顶部位置 - 情况2和情况3虽然描述不同,但操作方法是一样的。
结果=牌堆所有数字位置合理时需要操作的最大值+牌堆数字个数
具体步骤
1.定义一个函数hasSequentialSegment用于判断牌堆底部是否有以1开头的连续递增子序列。它通过遍历牌堆底部,找到1的位置,然后判断后续的数字是否连续递增,如果是则返回true,否则返回false。
// 判断牌堆底部是否有1开头的连续的子序列
bool hasSequentialSegment(const vector<int>& pile) {int k = 0;int num = 2;for (int i = 1; i < pile.size(); i++) {//找到1的位置if (pile[i] == 1) {k = i+1;break;}
}while (pile[k] == num) {//判断是否连续num++;k++;}//如果子序列从1开始连续递增直至牌堆底部,则返回trueif (k == pile.size()) return true;return false;//没有则返回false
}
2.定义一个函数calculateResult用于计算最少执行的操作数。首先判断牌堆底部是否有以1开头的连续递增子序列,如果有,再判断牌堆其他数字的位置是否满足条件。如果满足条件(情况一),则结果为1的位置减去牌堆顶部位置。如果不满足条件(情况二、三),则需要计算使牌堆所有数字位置合理时需要操作的最大值,即遍历牌堆中的数字,找到使数字位置合理的最大差值。最后,结果为牌堆所有数字位置合理时需要操作的最大值加上牌堆的数字个数。
// 计算最少执行的操作数
int calculateResult(const vector<int>& pile) {int result = 0;int maxDiff = 0;// 如果牌堆底部中包含1开头的连续的递增子序列if (hasSequentialSegment(pile)) {int k = 0;int target = 0;int flag = 1;//用于标记递增子序列以外的数字位置是否合理//找到1的位置for (int i = 1; i <= pile.size() - 1; i++) {if (pile[i] == 1) {k = i;break;}}target = pile.size() - k;//标记1开头连续子序列的最后一个数字for (int j = 1; j < k; j++) {//遍历1前面的数字,判断这个数字当前的位置是否合理if (pile[j] > target&& j + 1 > pile[j] - target) {flag = 0;//如果不合理,break;}}//计算操作次数,分为两种情况// 第一种情况:牌堆底部有1开头连续递增子序列且牌堆其他数字满足位置条件if (flag == 1) {result = k - 1;//结果=1的位置-牌堆顶部位置return result;}}//第二种情况:①牌堆底部没有1开头的递增子序列②牌堆底部有1开头的连续子序列但牌堆其他数字不满足位置条件// 计算使牌堆所有数字位置合理时需要操作的最大值for (int i = 1; i <= pile.size()-1; i++) {if (i >= pile[i] && pile[i] != 0) {maxDiff = max(maxDiff, i - pile[i] + 1);}}result = maxDiff + pile.size()-1;//结果=牌堆所有数字位置合理时需要操作的最大值+牌堆的数字个数return result;
}
3.在主函数中,首先读入输入的牌堆大小n,然后分别读入手牌和牌堆的数字。调用calculateResult函数计算最少执行的操作数,并输出结果。
int main() {int n;cin >> n;vector<int> hand(n + 1), pile(n + 1);for (int i = 1; i <= n; i++) {cin >> hand[i];}for (int i = 1; i <= n; i++) {cin >> pile[i];}int result = calculateResult( pile);cout << result << endl;return 0;
}
C++整体代码(含详细注释)
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 判断牌堆底部是否有1开头的连续的子序列
bool hasSequentialSegment(const vector<int>& pile) {int k = 0;int num = 2;for (int i = 1; i < pile.size(); i++) {//找到1的位置if (pile[i] == 1) {k = i+1;break;}
}while (pile[k] == num) {//判断是否连续num++;k++;}//如果子序列从1开始连续递增直至牌堆底部,则返回trueif (k == pile.size()) return true;return false;//没有则返回false
}// 计算最少执行的操作数
int calculateResult(const vector<int>& pile) {int result = 0;int maxDiff = 0;// 如果牌堆底部中包含1开头的连续的递增子序列if (hasSequentialSegment(pile)) {int k = 0;int target = 0;int flag = 1;//用于标记递增子序列以外的数字位置是否合理//找到1的位置for (int i = 1; i <= pile.size() - 1; i++) {if (pile[i] == 1) {k = i;break;}}target = pile.size() - k;//标记1开头连续子序列的最后一个数字for (int j = 1; j < k; j++) {//遍历1前面的数字,判断这个数字当前的位置是否合理if (pile[j] > target&& j + 1 > pile[j] - target) {flag = 0;//如果不合理,break;}}//计算操作次数,分为两种情况// 第一种情况:牌堆底部有1开头连续递增子序列且牌堆其他数字满足位置条件if (flag == 1) {result = k - 1;//结果=1的位置-牌堆顶部位置return result;}}//第二种情况:①牌堆底部没有1开头的递增子序列②牌堆底部有1开头的连续子序列但牌堆其他数字不满足位置条件// 计算使牌堆所有数字位置合理时需要操作的最大值for (int i = 1; i <= pile.size()-1; i++) {if (i >= pile[i] && pile[i] != 0) {maxDiff = max(maxDiff, i - pile[i] + 1);}}result = maxDiff + pile.size()-1;//结果=牌堆所有数字位置合理时需要操作的最大值+牌堆的数字个数return result;
}int main() {int n;cin >> n;vector<int> hand(n + 1), pile(n + 1);for (int i = 1; i <= n; i++) {cin >> hand[i];}for (int i = 1; i <= n; i++) {cin >> pile[i];}int result = calculateResult( pile);cout << result << endl;return 0;
}
相关文章:
15. 卡牌游戏
目录 题目 思路 C整体代码(含详细注释) 题目 Description 小张在玩一种卡牌游戏,牌组由张牌组成,其中张上写有数字各一张,其余张上全部是数字。 现在牌组经过随机打乱后,小张拿走其中张牌作为手牌&#…...
vue使用打印组件print-js
项目场景: 由于甲方要求,项目需要打印二维码标签,故开发此功能 开发流程 安装包:npm install print-js --saveprint-js的使用 <template><div id"print" ref"print" ><p>打印内容<p&…...
20230830比赛总结
分数 预估分数: 100 100 [ 0 , 20 ] 100 [ 300 , 320 ] 100100[0,20]100[300,320] 100100[0,20]100[300,320] 实际分数: 100 100 10 100 310 10010010100310 10010010100310 反思 B 只是粗略观察表就急于写决策单调性优化,写完后…...
DNS指向别名还是IP
现在有一台服务器dbprod126,ip是172.22.100.4 现在有一个需求,需要在dns中对dbprod126建一个别名wondadb3r的记录,也就是ping wondadb3r的时候显示的是dbprod126的ip,目前有两种方法,主要使用方法1指向别名…...
【考研数学】概率论与数理统计 —— 第二章 | 一维随机变量及其分布(1,基本概念与随机变量常见类型)
文章目录 引言一、一维随机变量及其分布1.1 随机变量1.2 分布函数 二、随机变量常见类型及分布2.1 离散型随机变量2.2 连续型随机变量及概率密度函数 写在最后 引言 暑假接近尾声了,争取赶一点概率论部分的进度。 一、一维随机变量及其分布 1.1 随机变量 设随机试…...
CSS判断手机暗黑模式
手机有个功能到了晚上会自动变成深色也就是暗黑模式.这种情况下网页会自动变颜色.如果想自由控制暗黑模式下的html样式的话,可以用如下方式: media (prefers-color-scheme: dark) {/*html, body {*//*filter: invert(1) hue-rotate(180deg);*//*}*/.maill{margin-left: 0;marg…...
【java中的Set集合】HashSet、LinkedHashSet、TreeSet(最通俗易懂版!!)
目录 一、HashSet集合 1.HashSet集合的特点 2.HashSet常用方法 二、LinkedHashSet集合 LinkedHashSet集合的特点 三、TreeSet集合 1.TreeSet集合的特点 2.TreeSet的基本使用 四、HashSet、LinkedHashSet、TreeSet的使用场景 五、list和set集合的区别 一、HashSet集合 …...
python中的文件操作
我们平常对文件的基本操作,大概可以分为三个步骤(简称文件操作三步走): ① 打开文件 ② 读写文件 ③ 关闭文件 【注意事项】 注意:可以只打开和关闭文件,不进行任何读写 文件打开 open函数ÿ…...
spark支持深度学习批量推理
背景 在数据量较大的业务场景中,spark在数据处理、传统机器学习训练、 深度学习相关业务,能取得较明显的效率提升。 本篇围绕spark大数据背景下的推理,介绍一些优雅的使用方式。 spark适用场景 大数据量自定义方法处理、类sql处理传统机器…...
代码随想录打卡—day52—【子序列问题】— 8.31 最大子序列
共性 做完下面三题,发现三个的dp数组中i都是以 i 为结束的字串。 1 300. 最长递增子序列 300. 最长递增子序列 AC: class Solution { public:int dp[10010]; // 表示以i结束的子序列最大的长度/*if(nums[j] > nums[i])dp[j] max(dp[j],dp[i] …...
gcc4.8.5升级到gcc4.9.2
第1步:获取repo [rootlocalhost SPECS]# wget --no-check-certificate https://copr.fedoraproject.org/coprs/rhscl/devtoolset-3/repo/epel-6/rhscl-devtoolset-3-epel-6.repo -O /etc/yum.repos.d/devtoolset-3.repo --2021-12-07 20:53:26-- https://copr.fedo…...
Golang 中的 archive/zip 包详解(三):常用函数
Golang 中的 archive/zip 包用于处理 ZIP 格式的压缩文件,提供了一系列用于创建、读取和解压缩 ZIP 格式文件的函数和类型,使用起来非常方便,本文讲解下常用函数。 zip.OpenReader 定义如下: func OpenReader(name string) (*R…...
微服务架构七种模式
微服务架构七种模式 目录概述需求: 设计思路实现思路分析 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,full busy,skip hardness,make a better result,wait for change,challenge Survive.…...
关于CICD流水线的前端项目运行错误,npm项目环境配置时出现报错:Not Found - GET https://registry.npm...
关于CICD流水线的前端项目运行错误,npm项目环境配置时出现报错:Not Found - GET https://registry.npm… 原因应该是某些jar包缓存中没有需要改变镜像将包拉下来 npm config set registry http://registry.npm.taobao.org npm install npm run build...
element-plus的周选择器 一周从周一开始
1、代码 1)、template中 <el-date-picker v-model"value1" type"week" format"[Week] ww" placeholder"巡访周" change"change"value-format"YYYY-MM-DD" /> 2)、方法中 import…...
Android 9.0 pms获取应用列表时过滤掉某些app功能实现
1.前言 在9.0的系统rom定制化开发中,对系统定制的功能也是很多的,在一次产品开发中,要求在第三方app获取应用列表的时候,需要过滤掉某些app,就是不显示在app应用列表中,这就需要在pms查询app列表时过滤掉这些app就可以了,接下来就实现这些功能 2.pms获取应用列表时过滤掉…...
HTML <thead> 标签
实例 带有 thead、tbody 以及 tfoot 元素的 HTML 表格: <table border="1"><thead><tr><th>Month</th><th>Savings</th></tr></thead><tfoot><tr><td>Sum</td><td>$180<…...
谷歌发布Gemini以5倍速击败GPT-4
在Covid疫情爆发之前,谷歌发布了MEENA模型,短时间内成为世界上最好的大型语言模型。谷歌发布的博客和论文非常可爱,因为它特别与OpenAI进行了比较。 相比于现有的最先进生成模型OpenAI GPT-2,MEENA的模型容量增加了1.7倍…...
力扣92. 局部反转链表
92. 反转链表 II 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left < right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 示例 1: 输入:head [1,2,3,4,5], left 2, right 4 输出&am…...
九、适配器模式
一、什么是适配器模式 适配器模式(Adapter)的定义如下:将一个类的接口转换成客户希望的另外一个接口,使得原本由于接口不兼容而不能一起工作的那些类能一起工作。 适配器模式(Adapter)包含以下主要角色&…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
