まさに「座標圧縮」をしてください、という問題!
問題概要
個の整数 が与えられる。それぞれについて、「大きい順に何番目か」を求めよ。
たとえば に対しては、答えは となる。
制約
前提知識
座標圧縮について知っておきましょう!
考えたこと
今回の問題のように、小さい順または大きい順に番号付けするのは、ぞくに「座標圧縮」と呼ばれる。より難しい問題の前処理として頻繁に登場する。本来の座標圧縮では、タイは除外する (上の例では 90 と 100 のタイは除外して とする) ことが多いのでちょっと違うけど...。
さて、「大きい順」というのが考えづらいので、あらかじめ の各要素に対して
A[i] = 100 - A[i];
とすることにする。こうすれば「小さい順に何番目か」という問題になって扱いやすくなる。その後は次のようにする。
- を小さい順にソートした配列を とする
- 各
A[i]
に対してlower_bound(S.begin(), S.end(), A[i]) - S.begin()
を求める
これで求められる。ただしこのままでは 0-indexed なので 1-indexed に直して出力する。計算量は 。
コード
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; ++i) cin >> A[i], A[i] = 100-A[i]; auto S = A; sort(S.begin(), S.end()); for (int i = 0; i < N; ++i) { int res = lower_bound(S.begin(), S.end(), A[i]) - S.begin(); ++res; cout << res << endl; } }