UVa 482 Permutation Arrays

题目描述题目要求根据给定的索引数组ppp对数据数组xxx进行重排。索引数组ppp包含111到nnn的整数不一定按顺序表示新数组中每个位置上的元素在原数组中的索引。即xpi′xix_{p_i} x_ixpi​′​xi​。给定ppp和xxx输出重排后的数组x′xx′每行一个元素。输入格式第一行一个整数NNN表示测试用例的数量后面跟一个空行。每个测试用例包含两行第一行nnn个整数表示索引数组ppp。第二行nnn个浮点数或其他格式的数字表示数据数组xxx。两个连续测试用例之间由一个空行分隔。输出格式对于每个测试用例输出nnn行每行一个重排后的数据按x′xx′的顺序即位置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′xx′大小为nnn。对于每个iii000到n−1n-1n−1设置x′[pi−1]x[i]x[p_i - 1] x[i]x′[pi​−1]x[i]。按顺序输出x′xx′。注意点索引数组中的值是从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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);for(inti1;icases;i){if(i1)coutendl;vectorintorder;vectorstringnumber;getline(cin,line);getline(cin,line);istringstreamiss(line);intindex;while(issindex)order.push_back(index);getline(cin,line);iss.clear();iss.str(line);string block;while(issblock)number.push_back(block);vectorintoutput(order.size());for(intj0;jorder.size();j)output[order[j]-1]j;for(intj0;joutput.size();j)coutnumber[output[j]]\n;}return0;}