题目
小明同学把1到n这n个数字按照一定的顺序放入了一个队列Q中。现在他对队列Q执行了如下程序：
while(!Q.empty()) //队列不空，执行循环 { int x=Q.front(); //取出当前队头的值x Q.pop(); //弹出当前队头 Q.push(x); //把x放入队尾 x=Q.front(); //取出这时候队头的值 printf("%d\n",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#include #include using namespace std;/*示例输入412310*//*示例输出1 2 1 2 1 38 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 reflection; queue 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 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 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;}