题目
小明同学把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 <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;
}
原文链接: https://www.cnblogs.com/rainySue/p/gou-zao-dui-lie.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/238996
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!