目录
一、问题描述
问题描述
体育老师小明要将自己班上的学生按顺序排队。他首先让学生按学号从小到大的顺序排成一排，学号小的排在前面，然后进行多次调整。一次调整小明可能让一位同学出队，向前或者向后移动一段距离后再插入队列。
例如，下面给出了一组移动的例子，例子中学生的人数为8人。
0）初始队列中学生的学号依次为1, 2, 3, 4, 5, 6, 7, 8；
1）第一次调整，命令为“3号同学向后移动2”，表示3号同学出队，向后移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 3, 6, 7, 8；
2）第二次调整，命令为“8号同学向前移动3”，表示8号同学出队，向前移动3名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 5, 8, 3, 6, 7；
3）第三次调整，命令为“3号同学向前移动2”，表示3号同学出队，向前移动2名同学的距离，再插入到队列中，新队列中学生的学号依次为1, 2, 4, 3, 5, 8, 6, 7。
小明记录了所有调整的过程，请问，最终从前向后所有学生的学号依次是多少？
请特别注意，上述移动过程中所涉及的号码指的是学号，而不是在队伍中的位置。在向后移动时，移动的距离不超过对应同学后面的人数，如果向后移动的距离正好等于对应同学后面的人数则该同学会移动到队列的最后面。在向前移动时，移动的距离不超过对应同学前面的人数，如果向前移动的距离正好等于对应同学前面的人数则该同学会移动到队列的最前面。
输入格式
输入的第一行包含一个整数n，表示学生的数量，学生的学号由1到n编号。
第二行包含一个整数m，表示调整的次数。
接下来m行，每行两个整数p, q，如果q为正，表示学号为p的同学向后移动q，如果q为负，表示学号为p的同学向前移动-q。
输出格式
输出一行，包含n个整数，相邻两个整数之间由一个空格分隔，表示最终从前向后所有学生的学号。
样例输入
8
3
3 2
8 -3
3 -2
样例输出
1 2 4 3 5 8 6 7
评测用例规模与约定
对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000，所有移动均合法。
二、解答
方法1：使用数组
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int n;
cin >> n;
int a[1001] = { 0 };
for (int i = 1; i <= n; i++)
{
a[i] = i;
}
int m;
cin >> m;
int p[1001] = { 0 };
int q[1001] = { 0 };
for (int i = 0; i < m; i++)
{
cin >> p[i] >> q[i];//这里不需要数组，直接输入p、q也行
if (q[i] > 0)
{
int j = 1;
while (a[j] != p[i])
{
j++;
}
for (int k = 0; k < q[i]; k++)
{
int x = a[j];//进行交换
a[j] = a[j + 1];
a[j + 1] = x;
j++;
}
}
else {
int j = 1;
while (a[j] != p[i])
{
j++;
}
for (int k = 0; k < abs(q[i]); k++)
{
int x = a[j];
a[j] = a[j - 1];
a[j - 1] = x;
j--;
}
}
}
for (int i = 1; i <= n; i++)
{
cout << a[i] << " ";
}
return 0;
}方法2：使用vector容器
注意：①vi[i] 和 *(vi.begin() + i) 等价；②v.erase(v.begin() + j,i);表示在v[j]处插入i或者i取代掉原来的v[j],原来的v[j]及其后面的元素依次向后移动1位
代码：
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int>v;
for (int i = 1; i <= n; i++)
{
v.push_back(i);
}
int m;
cin >> m;
for (int i = 0; i < m; i++)
{
int p, q;
cin >> p >> q;
int j = 0;
while(v[j]!=p)
{
j++;
}
//方式1：先删除，后插入，不必考虑q是否大于0或小于0
v.erase(v.begin() + j);
v.insert(v.begin() + j + q, p);
//方式2：先插入，后删除，要考虑q是否大于0或小于0
//注意：这样写即先插入后删除得不到正确的结果
//v.insert(v.begin() + j + q + 1, p);
//v.erase(v.begin() + j);
// 这种操作顺序导致在此时插入的元素会改变原始向量的结构，可能会导致插入到错误的位置。
// 原因在于：没有考虑q<0的情况
//如果想要先插入后删除，就要分情况，因为向前移动和向后移动对其他元素的影响是不一样的
// 正确写法：
//if(q>0)
//{ v.insert(v.begin() + j + q + 1, p);//后一位
//v.erase(v.begin() + j);}
//else {
// v.insert(v.begin() + j + q , p);
// v.erase(v.begin() + j+1);
//}
}
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
return 0;
}三、总结
刚开始看这一题的时候，第一反应是用链表，但是写着写着，发现如果用链表的话就太复杂了，还要设置两个指针，弄成双向链表，因为还有1个向前移动。然后我想到数组之间的交换，就转而用数组的方式，没有用很长时间，自然而然就写出来了。上网搜索发现巧妙与熟练运用vector的方法也不是很难。
综上，说实话，这道题目真的不难，只是我一开始就想的太复杂了，耽误了很长时间。我也不知道为什么有时候我就总会把简单问题复杂化，归根结底，可能还是我本身能力的问题吧。还是得加强思维上的锻炼啊。
另外，谨记：在弄不清楚或者糊涂的时候，自己可以多举几个示例进行模拟与总结！！！
标签：同学,begin,移动,学号,int,201703,++,CCF,CSP From： https://blog.csdn.net/2301_79705447/article/details/141939451