この問題で要求している処理を「前処理」として要求する問題はたくさんある!!! というわけで教育的な問題かもしれない。
問題概要
人の生徒がいて、出席番号 の生徒はそれぞれ、全体で 人目に登校していることがわかっている。
これらの情報を元にして、生徒の出席番号を、登校が早い順に並び替えよ。
制約
考えたこと
いわゆる逆順列を求める問題だね。逆順列というのは...
たとえばしたのような順列 ( の並び替えのこと) が与えられたとする。
1 2 3 4 5 6 7 6 5 2 4 3 7 1
この上下の対応を保ったまま、下を 1, 2, ... の順に並び替える。
7 3 5 4 2 1 6 1 2 3 4 5 6 7
このとき、順列 (7, 3, 5, 4, 2, 1, 6) は、順列 (6, 5, 2, 4, 3, 7, 1) の逆順列であるという。
逆順列の求め方
プログラム的には順列は 0 始まりで考えた方が考えやすい。このとき順列 の逆順列 は
for (int i = 0; i < N; ++i) Q[P[i]] = i
と簡潔に求めることができる。つまり逆順列 Q においては
- i は P[i] 番目の要素である
ということになる。なので Q[ P[ i ] ] = i とすれば OK。
#include <iostream> #include <vector> using namespace std; int main() { int N; cin >> N; vector<int> P(N), Q(N); for (int i = 0; i < N; ++i) cin >> P[i], --P[i]; for (int i = 0; i < N; ++i) Q[P[i]] = i; for (int i = 0; i < N; ++i) cout << Q[i]+1 << " "; cout << endl; }