题目描述

题目要求根据给定的索引数组ppp对数据数组xxx进行重排。索引数组ppp包含111到nnn的整数（不一定按顺序），表示新数组中每个位置上的元素在原数组中的索引。即xpi′=xix'_{p_i} = x_ixpi​′​=xi​。给定ppp和xxx，输出重排后的数组x′x'x′，每行一个元素。

输入格式

第一行一个整数NNN，表示测试用例的数量，后面跟一个空行。每个测试用例包含两行：

• 第一行：nnn个整数，表示索引数组ppp。
• 第二行：nnn个浮点数（或其他格式的数字），表示数据数组xxx。
  两个连续测试用例之间由一个空行分隔。

输出格式

对于每个测试用例，输出nnn行，每行一个重排后的数据，按x′x'x′的顺序（即位置111到nnn）。两个连续测试用例的输出之间由一个空行分隔。

样例

输入

1 3 1 2 32.0 54.7 -2

输出

54.7 -2 32.0

题目分析

本题的核心是根据索引数组ppp将数据数组xxx重新排列。关系为xpi′=xix'_{p_i} = x_ixpi​′​=xi​，即原数组的第iii个元素应放在新数组的第pip_ipi​个位置。

算法步骤

1. 读取索引数组ppp，长度为nnn。
2. 读取数据数组xxx，长度也为nnn。
3. 创建结果数组x′x'x′，大小为nnn。
4. 对于每个iii（000到n−1n-1n−1），设置x′[pi−1]=x[i]x'[p_i - 1] = x[i]x′[pi​−1]=x[i]。
5. 按顺序输出x′x'x′。

注意点

• 索引数组中的值是从111开始的，需要转换为000索引。
• 数据数组中的数字可能包含负号、小数点等，应作为字符串原样输出（以保留原始格式）。
• 输入中可能有多余的空格或空行，需要正确处理。

复杂度分析

时间复杂度O(n)O(n)O(n)，空间复杂度O(n)O(n)O(n)。

代码实现

// Permutation Arrays// UVa ID: 482// Verdict: Accepted// Submission Date: 2016-07-15// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcases=stoi(line);for(inti=1;i<=cases;i++){if(i>1)cout<<endl;vector<int>order;vector<string>number;getline(cin,line);getline(cin,line);istringstreamiss(line);intindex;while(iss>>index)order.push_back(index);getline(cin,line);iss.clear();iss.str(line);string block;while(iss>>block)number.push_back(block);vector<int>output(order.size());for(intj=0;j<order.size();j++)output[order[j]-1]=j;for(intj=0;j<output.size();j++)cout<<number[output[j]]<<'\n';}return0;}