题目
小明同学把1到n这n个数字按照一定的顺序放入了一个队列Q中。现在他对队列Q执行了如下程序：
while(!Q.empty()) //队列不空，执行循环
{
int x=Q.front(); //取出当前队头的值x
Q.pop(); //弹出当前队头
Q.push(x); //把x放入队尾
x=Q.front(); //取出这时候队头的值
printf("%d
",x); //输出x
Q.pop(); //弹出这时候的队头
}
做取出队头的值操作的时候，并不弹出当前队头。
小明同学发现，这段程序恰好按顺序输出了1,2,3,...,n。现在小明想让你构造出原始的队列，你能做到吗？
输入
第一行一个整数T（T<=100）表示数据组数，每组数据输入一个数n（1<=n<=100000），输入的所有n之和不超过200000。
输出
对于每组数据，输出一行，表示原始的队列。数字之间用一个空格隔开，不要在行末输出多余的空格。
样例输入
4
1
2
3
10
样例输出
1
2 1
2 1 3
8 1 6 2 10 3 7 4 9 5
法一
一个数字数列按顺序进入队列并依照题干进行操作后，实际上输出的序列是原序列的一个映射，只要找出这种映射关系，那么就可以根据输出序列构造输入序列
因此，此方法包含两个步骤
- 找出序列变换前后的位置映射关系
- 根据映射关系以及输出数组构造输入数组
源程序
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
/*示例输入
4
1
2
3
10
*/
/*示例输出
1
2 1
2 1 3
8 1 6 2 10 3 7 4 9 5
*/
void Construct(int n)
{
//记录队列中的序列经过处理后的前后位置映射。
//起初reflection[i] = i,存储old_index;(此处省略初始化reflection元素过程，直接将对应的数据插入queue中)
//处理后，有old_index = reflection[new_index]
// 对于输入输出序列存在如下关系：output[new_index] = input[old_index]
// 亦即：output[new_index] = input[reflection[new_index]]
vector<int> reflection;
queue<int> que;
for(int i = 0;i < n;++ i)
{
que.push(i);
}
while(!que.empty())
{
int tmp = que.front();
que.pop();
que.push(tmp);
int num = que.front();
reflection.push_back(num);
que.pop();
}
// 根据题意，输出序列为，output[i] = i + 1;
// 根据输出序列赋值输入序列对应位置的值,即input[reflection[i]] = output[i] = i + 1;
std::vector<int> input(n);
for(int i = 0;i < n;++ i)
{
input[reflection[i]] = i + 1;
}
for(int i = 0;i < n;++ i)
{
cout << input[i] << " ";
}
cout << endl;
}
int main()
{
int t,n;
cin >> t;
for(int i = 0;i < t;++ i)
{
cin >> n;
Construct(n);
}
return 0;
}
法二
分析对序列的操作，可以发现其实是对queue中剩余的序列的偶数位输出，奇数位重新插入数组，如此重复直到queue为空
按照此规律将输出数列填入合适的位置，即可构造原始的输入数列
- 未处理的元素（对应于仍在queue中的数字）为初始化值（此处为设为0）
- count表示下一个需要填入的数字
- flag用于指示是否填入输出（对应于queue中是否输出数字）
源程序
void OtherConstruct(int n)
{
/*未处理的元素（对应于仍在queue中的数字）为初始化值（此处为设为0）
*count表示下一个需要填入的数字
*flag用于指示是否填入输出（对应于queue中是否输出数字）
*/
int count = 1;
int flag = 0;
vector<int> data(n);
while(count <= n)
{
for(int i = 0;i < n;++ i)
{
if(data[i] == 0)
{
//此位置还没有元素
flag ++;
if(flag % 2 == 0)
{
data[i] = count;
count ++;
}
}
}
}
for(int i = 0;i < n;++ i)
cout << data[i] << " ";
cout << endl;
}