UVa 482 Permutation Arrays
题目描述
题目要求根据给定的索引数组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个位置。
算法步骤
- 读取索引数组ppp，长度为nnn。
- 读取数据数组xxx，长度也为nnn。
- 创建结果数组x′x'x′，大小为nnn。
- 对于每个iii（000到n−1n-1n−1），设置x′[pi−1]=x[i]x'[p_i - 1] = x[i]x′[pi−1]=x[i]。
- 按顺序输出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;}