首页 > ACM题库 > HDU-杭电 > HDU 4657-Find Permutation[解题报告]HOJ
2015
09-17

HDU 4657-Find Permutation[解题报告]HOJ

Find Permutation

问题描述 :

Given b0, b1, …, bn-1, find two permutations {ai}, {ci} of 0..n-1 such that ai+bi=ci (mod n) for every i.

输入:

First line, number of test cases, T.
Following are 2*T. For every two lines, the first line is n and the second line contains n integers.

Sum of all n <= 105.
0<=bi<n
It’s guaranteed that there exists a solution.
Test data is generated by randomly choosing two permutations and subtracting one from the other.

输出:

First line, number of test cases, T.
Following are 2*T. For every two lines, the first line is n and the second line contains n integers.

Sum of all n <= 105.
0<=bi<n
It’s guaranteed that there exists a solution.
Test data is generated by randomly choosing two permutations and subtracting one from the other.

样例输入:

1
3
0 1 2

样例输出:

2 0 1
2 1 0

题目链接:hdu 4657 Find Permutation

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 1e5 + 5;

int N, A[maxn], B[maxn], C[maxn], P[maxn];

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) scanf("%d", &B[i]);
        for (int i = 0; i < N; i++) A[i] = C[i] = P[i] = i;

        for (int i = 0; i < N; i++) {
            int u = i;
            while ((A[u] + B[u]) % N != C[u]) {
                int v = P[(C[u] - B[u] + N) % N];
                swap(A[u], A[v]);
                swap(P[A[u]], P[A[v]]);

                if (v > i) break;
                swap(C[i+1], C[v]);
                u = v;
            }
        }
        for (int i = 0; i < N; i++) printf("%d%c", A[i], i == N-1 ? '\n' : ' ');
        for (int i = 0; i < N; i++) printf("%d%c", C[i], i == N-1 ? '\n' : ' ');
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/keshuai19940722/article/details/49688021