程序设计方法与实践/小学期）"/>
【第十一题】卡牌游戏（北理工/北京理工大学/程序设计方法与实践/小学期）
目录
Description
核心思路：创建映射
舍友的源码
我自己码出来的第一份源码
debug
修正后的源码：
事后反思：
Description
小张在玩一种卡牌游戏，牌组由 2n 张牌组成，其中 n 张上写有数字 1...n 各一张，其余 n 张上全部是数字 0 。
现在牌组经过随机打乱后，小张拿走其中 n 张牌作为手牌，其余 n 张牌作为牌堆。
小张想经过若干次如下操作使得牌堆自顶向下的牌依次为 1...n 。 每一次操作，小张选择任意一张手牌放到牌堆底，并将牌堆顶的牌放入手牌。
他想知道最少进行几次操作，使得牌堆自顶向下的牌依次为 1...n 。
Input
第一行一个数 n(1 \leq n \leq 200000 ) 。
第二行 n 个数，表示小张手中的牌。
第三行 n 个数，表示牌堆，数组从左向右的顺序表示牌堆自顶向下的顺序。
Output
一个整数，表示最少执行的操作数。
核心思路：创建映射
这题拿到后，会发现信息不足，这时就要创造另外一系列信息，然后通过两个信息作用出第三种信息。
说的很抽象，就拿T2（解谜游戏），T9（子序列自动机），T11（卡牌游戏）来说。
T2 是用puzzle记录初始键位，用press记录按键，用初始键位和按键作用后得出状态；T9是用子序列自动机来产生跳跃的链接；T11则是用index数组建立索引，通过索引和实际位置来得出需要的手数。
简单说，以后碰到难题，可以尝试新建一个数组，或者叫映射，来储存变化的信息，通过映射和原象的作用来进行判断计算。
舍友的源码
#include <cstdio>
int map[200005], stack[200005];
//map是第i张牌的索引，即实际位置,map==0代表手牌
//stack记录牌堆
int main(void)
{int n, temp, ans = 0, max = 0;bool flag = true, bol = true;scanf("%d", &n);for (int i = 0; i < n; i++)//标记手牌，0就是手牌，其他还没有初始化{scanf("%d", &temp);map[temp] = 0;}for (int i = 1; i <= n; i++){scanf("%d", &temp); // 索引到数字 （把实际数字放进牌堆）stack[i] = temp;// 数字到索引 (把堆里的实际位置写入map）map[temp] = i;}// 判断是否是从头到尾的连续序列 temp此时是尾部的数字,即将成为理想的连续串// n-1是指向倒数第二位stackfor (int i = n - 1; temp != 1; i--) {if (stack[i] != --temp){flag = false;break;}}if (flag) //成功走下来,那么temp==stack[i]&&temp==1//代表这是个连续的串，从1到stack[n]，但是1前面的东西不确定{for (int j = stack[n] + 1; j <= n; j++) {//map[j]肯定是在我们的stack==1的位置的前面//map[j]代表了要上手的操作数，j-（stack[n]+1)代表了操作空间，即几次操作后需要这张牌//比如561234，map[5]==1，所以要拿到5要一步，而5-(4+1)==0，留给你的操作数为0,所以不可能一轮搞定//map[j] == 0 ||没有必要,大概是为了可读性,其实map[j]为0的时候，就已经满足后面条件了//因为不管留给你多少操作数，我已经不需要操作了if ( map[j] <= j - (stack[n] + 1))//操作数满足操作空间的，就看下一个{continue;}else {bol = false;break;}}if (bol)//代表剩下那n-stack[n]个数都满足操作空间限制，那就一轮过{ans += n - stack[n];}else //不能一轮走完，那就再多走一轮 1+n 步，变成001234，再一轮过{ //为什么走一轮会是n+1呢？因为还得在手上倒一下,实际上我们的环长是n+1ans += 1 + n + n - stack[n];}}else //没有完整走下来此时，i和stack[i]是不相等的,至此断开连续{//如216345但是从n到i-1是连续的，但是连续序列首部不是1for (int i = 1; i <= n; i++) //一般来说这个max会对应到1上，或者说在走到max步的时候，1已经在手了{temp = (map[i] - i + 1) > 0 ? (map[i] - i + 1) : 0;if (temp > max){max = temp;}}ans += n; //所有操作数都满足操作空间限制，开始放1，顺次放完ans += max;}printf("%d\n", ans);return 0;
}我自己码出来的第一份源码
错了两个，有漏洞，一定是我哪里写的有问题，但是请记住，不要用错误的思维去遍历一个错误的答案。
//本题核心:
//index[i]的含义：索引，或者说是我要拿到这张牌需要的操作数
//i-(card[n]+1)代表如果要从结尾顺着连到i，要用i牌之前，留给你的操作空间
//561234那么5-(4+1)==0，也就是说没有操作空间，必须手上有牌
//6-(4+1)==1，给6留了1手的空间
#include<stdio.h>
#include<stdbool.h>
int max(int a, int b) { return a > b ? a : b; };
void input(void);
bool CanToOne(void);
void judge(bool);#define SIZE 200010
int index[SIZE], card[SIZE];//index为索引，0代表手牌 card是实际牌int temp, n, i, ans = 0, steps = 0;//在所有函数中都要用，所以作用域弄成全局int main(void)
{input();judge(CanToOne());printf("%d\n", ans);return 0;
}void input(void)
{scanf("%d", &n);for (i = 1; i <= n; i++)//记录手牌{scanf("%d", &temp);index[temp] = 0;}for (i = 1; i <= n; i++){scanf("%d", &temp);//装入牌堆，下标为位置，内容为牌面card[i] = temp;//为card建立索引,下标为牌面，内容为位置index[temp] = i;}
}
bool CanToOne(void)//包含极端情况，连续串长度为1，即不连续
{int temp;temp = card[n];//temp是末尾数字for (i = n - 1; temp > 1; i--) //i指向倒数第二,--temp代表理想连续if (card[i] != --temp)return false;return true;//能走下来就是true
}
void judge(bool success)
{bool oneloop = true; //假设可以一轮走完if (success) //序列是从1到card[n]的，可以考虑一遍过{for (i = card[n] + 1; i <= n; i++)//寻找剩下n-stack[n]张牌{if (index[i] > i - (card[n] + 1))//所需超过空间{oneloop = false;break;}}if (oneloop)//可以一轮走完的情况ans += n - card[n];//把剩余的牌填上else //一轮搞不定，那就先走一轮n+1，把手牌全获取了，然后把剩余的牌填进去ans += n + 1 + n - card[n]; }else //序列没有走到1，先考虑怎么获得1再说吧{for (i = 1; i <= n; i++)//计算缺少的最大操作数{temp = max(index[i] - (i - (0 + 1)), 0);//因为我们是打算从1开始放，所以就把最后一张用0if (temp > steps)steps = temp; }ans += steps;//补上操作数，此时满足从1开始的一遍过条件ans += n;}
}debug
我采用的办法是：把舍友的代码改成函数式
这是舍友源码函数化的源码
#include<stdio.h>
#include<stdbool.h>
int index[200005], card[200005];
int n, temp, ans = 0, max = 0;
bool flag = true, bol = true;
void input(void);
bool CanToOne(void);
void iudge(bool success);
int main(void)
{input();iudge(CanToOne());printf("%d\n", ans);return 0;
}void input(void)
{scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &temp);index[temp] = 0;}for (int i = 1; i <= n; i++){scanf("%d", &temp);card[i] = temp;index[temp] = i;}
}
bool CanToOne(void)
{for (int i = n - 1; temp != 1; i--){if (card[i] != --temp){flag = false;break;}}return flag;
}
void iudge(bool success)
{if (success){for (int i = card[n] + 1; i <= n; i++){//index[i]肯定是在我们的card==1的位置的前面//index[i]代表了要上手的操作数，i-（card[n]+1)代表了操作空间，即几次操作后需要这张牌//比如561234，index[5]==1，所以要拿到5要一步，而5-(4+1)==0，留给你的操作数为0,所以不可能一轮搞定//index[i] == 0 ||没有必要,大概是为了可读性,其实index[i]为0的时候，就已经满足后面条件了//因为不管留给你多少操作数，我已经不需要操作了if (index[i] <= i - (card[n] + 1))//操作数满足操作空间的，就看下一个{continue;}else{bol = false;break;}}if (bol)//代表剩下那n-card[n]个数都满足操作空间限制，那就一轮过{ans += n - card[n];}else //不能一轮走完，那就再多走一轮 1+n 步，变成001234，再一轮过{ //为什么走一轮会是n+1呢？因为还得在手上倒一下,实际上我们的环长是n+1ans += 1 + n + n - card[n];}}else{for (int i = 1; i <= n; i++) //一般来说这个max会对应到1上，或者说在走到max步的时候，1已经在手了{temp = (index[i] - i + 1) > 0 ? (index[i] - i + 1) : 0;if (temp > max){max = temp;}}ans += n; //所有操作数都满足操作空间限制，开始放1，顺次放完ans += max;}
}ac了，说明函数结构没有问题。
然后就是一个函数一个函数地替换，终于在替换到CanToOne()函数地时候出现了同样的错误，emm，我感觉我写的没问题啊，破防了，但是至少缩小了范围！
我破防了，不管三七二十一，一个一个细节开始测试，我把条件换成temp!=1，就过了。
艹
本来我还想着说temp不是读取的牌堆吗，牌是从1-n的，这两个条件应该一样吧，但是，我忽略了0的情况，md！！！
修正后的源码：
//本题核心:
//index[i]的含义：索引，或者说是我要拿到这张牌需要的操作数
//i-(card[n]+1)代表如果要从结尾顺着连到i，要用i牌之前，留给你的操作空间
//561234那么5-(4+1)==0，也就是说没有操作空间，必须手上有牌
//6-(4+1)==1，给6留了1手的空间
#include<stdio.h>
#include<stdbool.h>
int max(int a, int b) { return a > b ? a : b; };
void input(void);
bool CanToOne(void);
void judge(bool);#define SIZE 200010
int index[SIZE], card[SIZE];//index为索引，0代表手牌 card是实际牌int temp, n, i, ans = 0, steps = 0;//在所有函数中都要用，所以作用域弄成全局int main(void)
{input();judge(CanToOne());printf("%d\n", ans);return 0;
}void input(void)
{scanf("%d", &n);for (i = 1; i <= n; i++)//记录手牌{scanf("%d", &temp);index[temp] = 0;}for (i = 1; i <= n; i++){scanf("%d", &temp);//装入牌堆，下标为位置，内容为牌面card[i] = temp;//为card建立索引,下标为牌面，内容为位置index[temp] = i;}
}
bool CanToOne(void)//包含极端情况，连续串长度为1，即不连续
{int temp;temp = card[n];//temp是末尾数字for (i = n - 1; temp != 1; i--) //i指向倒数第二,--temp代表理想连续if (card[i] != --temp)return false;return true;//能走下来就是true
}
void judge(bool success)
{bool oneloop = true; //假设可以一轮走完if (success) //序列是从1到card[n]的，可以考虑一遍过{for (i = card[n] + 1; i <= n; i++)//寻找剩下n-stack[n]张牌{if (index[i] > i - (card[n] + 1))//所需超过空间{oneloop = false;break;}}if (oneloop)//可以一轮走完的情况ans += n - card[n];//把剩余的牌填上else //一轮搞不定，那就先走一轮n+1，把手牌全获取了，然后把剩余的牌填进去ans += n + 1 + n - card[n]; }else //序列没有走到1，先考虑怎么获得1再说吧{for (i = 1; i <= n; i++)//计算缺少的最大操作数{temp = max(index[i] - (i - (0 + 1)), 0);//因为我们是打算从1开始放，所以就把最后一张用0if (temp > steps)steps = temp; }ans += steps;//补上操作数，此时满足从1开始的一遍过条件ans += n;}
}事后反思：
虽然修改出bug了，但是并不是一件坏事，这说明模块化+手打+自己的修改 ，用这种方式确实可以深入理解这个问题，在debug的时候用模块化也比较容易找出问题。
更多推荐
【第十一题】卡牌游戏（北理工/北京理工大学/程序设计方法与实践/小学期）
发布评论