目录
1.题目描述
编号为1…N的N个小朋友玩游戏，他们按编号顺时针围成一圈，从第一个人开始按逆时针次序报数，报到第M个人出列；
然后再从下个人开始按顺时针次序报数，报到第K个人出列；再从下一个人开始按逆时针次序报数，报到第M个人出列；再从下个人开始按顺时针次序报数，报到第K个人出列……
以此类推不断循环，直至最后一人出列。请编写程序按顺序输出出列人的编号。
输入为3个正整数，分别表示N、M、K，均不超过1000。
输出为一行整数，为出列人的编号。每个整数后一个空格。
2.输入输出
输入样例:
6 3 5
输出样例:
5 3 1 2 4 6
3.解题思路
这道题的话，我直接用一个数组来模拟，如果这个人出队的话，就将他标记为出队
这道题的难点是在如何实现题目的要求 ：一个顺时针，一个逆时针
对于这个要求，我选择使用一个方向向量 step ：
顺时针表示是 正方向 上的步数 ++
逆时针表示是 反方向 上的步数 ++
然后在每一次出队一个人后都更新一下 方向向量 和 出队要求（号数）
4.样例解析
以此类推
5.代码实现
当当前的号数还没喊道当前的规则时，就让下标往方向向量的位置运动
因为这个是一个环状结构，所以
当下标小于 1 的时候，传送到最后一个位置
当下标大于 n 的时候，传送到第一个位置
每次到达一个坐标的时候，都要判断一下当前这个号数的人是否出队
所以当前下标所对应的就是要出队的学生，将他的判断数组置为0
然后要记得到出队的下一个位置
step * -1 起到了转换方向向量的作用
利用三目操作符将操作的规则转换
最后要记得将 喊出的号数 重置为 1
AC代码
#include <iostream> using namespace std; const int N = 5010; int n, m, k; //逆时针 :k 顺时针 : m int q[N]; int main() { cin >> n >> m >> k; for(int i = 1; i <= n; i ++ ) q[i] = i; // 目前的编号 当前规则 下标 方向向量 int t = 1, rule = m, sig = 1, step = -1; for(int i = 1; i <= n; i ++ ) { while(t < rule) { sig += step; if(sig < 1) sig = n; if(sig > n) sig = 1; if(q[sig] != 0) t ++ ; } printf("%d ", sig); q[sig] = 0; sig += step; step *= -1; rule = (rule == m) ? k : m; t = 1; } return 0; }
1.题目描述
给定一个单链表 L1→L2→⋯→Ln−1→Ln，
请编写程序将链表重新排列为 Ln→L1→Ln−1→L2→⋯。
例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
2.输入输出
输入样例:
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例:
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
3.解题思路
这道题是一道链表的模拟题，我们要按照题目的要求来对所给的链表进行操作
注意到所有的地址不超过 1e5 所以我们直接使用数组的下标来作为地址方便运算
同时使用一个结构体来存储 数据 和 next指针
最后利用双指针算法 同时从两端开始来输出数据
按序输出地址即可
4.样例解析
初始条件
5.代码实现
创建地址结点，包含data和next
将起始地址和个数读入
然后依次读入地址，在对应的数组下标中读入相应的数据
定义一个 r 表示最右边的个数（总个数）
然后将当前的地址移动到第二个地址
当address ！= -1 的时候，一直递归处理，将链表中的地址按顺序存入a数组中
记得这一步 r -- 保证数据的准确性，不会多一个 ++
用a数组依次存储原链表的各个内存地址，b来模拟新的链表各个内存地址
利用双指针算法，题目要求将数组存入b数组中
AC代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; struct Node { int data, next; }q[N]; int a[N], b[N]; int main() { int next, n, address; cin >> next >> n; for(int i = 1; i <= n; i ++ ) { cin >> address; scanf("%d %d", &q[address].data, &q[address].next); } int r = 0; a[r ++ ] = next; address = q[next].next; while(address != -1) { a[r ++ ] = address; address = q[address].next; } r--; int l = 0, pos = 0; while(l <= r) { b[pos ++ ] = a[r -- ]; if(l <= r) b[pos ++ ] = a[l ++ ]; } for(int i = 0; i < pos; i ++ ) { if(i != pos - 1) printf("%05d %d %05d\n", b[i], q[b[i]].data,b[i + 1]); else printf("%05d %d -1", b[i], q[b[i]].data); } return 0; }
