网站备案 在哪里,上海建筑设计公司排名前20,马鞍山网站建设设计,wordpress 防cc目录 题目
思路
C整体代码#xff08;含详细注释#xff09; 题目
Description 小张在玩一种卡牌游戏#xff0c;牌组由张牌组成#xff0c;其中张上写有数字各一张#xff0c;其余张上全部是数字。 现在牌组经过随机打乱后#xff0c;小张拿走其中张牌作为手牌#…目录 题目
思路
C整体代码含详细注释 题目
Description 小张在玩一种卡牌游戏牌组由张牌组成其中张上写有数字各一张其余张上全部是数字。 现在牌组经过随机打乱后小张拿走其中张牌作为手牌其余张牌作为牌堆。 小张想经过若干次如下操作使得牌堆自顶向下的牌依次为。 每一次操作小张选择任意一张手牌放到牌堆底并将牌堆顶的牌放入手牌。 他想知道最少进行几次操作使得牌堆自顶向下的牌依次为。 Input 第一行一个数。 第二行个数表示小张手中的牌。 第三行个数表示牌堆数组从左向右的顺序表示牌堆自顶向下的顺序。 Output 一个整数表示最少执行的操作数
测试输入期待的输出时间限制内存限制额外进程测试用例 1以文本方式显示 3↵0 2 0↵3 0 1↵以文本方式显示 2↵1秒64M0测试用例 2以文本方式显示 3↵0 2 0↵1 0 3↵以文本方式显示 4↵1秒64M0 思路
手上的牌不重要重要的是牌堆里非0数字的位置有三种情况:
1牌堆最后存在1开头连续的数并且其他的数字均符合位置条件
2牌堆最后存在1开头连续的数但其他的数字不均符合位置条件
3牌堆最后不存在1开头连续的数
操作方法
情况1的操作方式一目了然直接把1前面的数字挤掉的同时在牌堆尾部添加相应的数字。结果1的位置-牌堆顶部位置情况2和情况3虽然描述不同但操作方法是一样的。结果牌堆所有数字位置合理时需要操作的最大值牌堆数字个数 具体步骤
1.定义一个函数hasSequentialSegment用于判断牌堆底部是否有以1开头的连续递增子序列。它通过遍历牌堆底部找到1的位置然后判断后续的数字是否连续递增如果是则返回true否则返回false。
// 判断牌堆底部是否有1开头的连续的子序列
bool hasSequentialSegment(const vectorint pile) {int k 0;int num 2;for (int i 1; i pile.size(); i) {//找到1的位置if (pile[i] 1) {k i1;break;}
}while (pile[k] num) {//判断是否连续num;k;}//如果子序列从1开始连续递增直至牌堆底部则返回trueif (k pile.size()) return true;return false;//没有则返回false
}
2.定义一个函数calculateResult用于计算最少执行的操作数。首先判断牌堆底部是否有以1开头的连续递增子序列如果有再判断牌堆其他数字的位置是否满足条件。如果满足条件情况一则结果为1的位置减去牌堆顶部位置。如果不满足条件情况二、三则需要计算使牌堆所有数字位置合理时需要操作的最大值即遍历牌堆中的数字找到使数字位置合理的最大差值。最后结果为牌堆所有数字位置合理时需要操作的最大值加上牌堆的数字个数。
// 计算最少执行的操作数
int calculateResult(const vectorint 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;vectorint 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 algorithmusing namespace std;// 判断牌堆底部是否有1开头的连续的子序列
bool hasSequentialSegment(const vectorint pile) {int k 0;int num 2;for (int i 1; i pile.size(); i) {//找到1的位置if (pile[i] 1) {k i1;break;}
}while (pile[k] num) {//判断是否连续num;k;}//如果子序列从1开始连续递增直至牌堆底部则返回trueif (k pile.size()) return true;return false;//没有则返回false
}// 计算最少执行的操作数
int calculateResult(const vectorint 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;vectorint 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;
}
