BOJ-18870座標圧縮ソリューション(C++)

題

  垂直線上のN個の座標X 1,X 2,...,XNがあります.この座標に座標圧縮を適用します.Xiを座標圧縮した後、X'iの値はXi>Xjを満たす異なる座標の個数に等しくなければならない.X1, X2, ..., XNに座標圧縮を適用すると、X"1,X"2,...,X'Nを印刷します.

入力

の最初の行にはNがあります.

行目は、スペースX 1、X 2、…、XNをあげます.

出力

  1行目X「1,X」2,...,X'Nをスペース出力に分割します.

制限
1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9

入力

例1
5
2 4 -10 4 -9

サンプル出力1
2 3 0 3 1

解決策
  基本ソートPS問題では最も深く考えるべき問題である.誰もが最初に問題に触れると、最も簡単なアルゴリズムが考えられます.これは,整列後にN個の整数を入力し,x[i]未満の要素個数を重畳した繰返し文で計算する方法である.ただし,Nは最大10,000個であるため,本アルゴリズムでは時間内に問題を解決することはできない.
  次に試してみる方法は、トポロジー組織の問題でよく使われる「値ベースの配列」です.しかし、これも近いうちに廃止されることがすぐにわかる.この値の範囲は10^9で、非常に大きいので、配列やベクトルを見つけるのは難しいです.
  上記の2つの試みが不可能であることに気づいた後、本科アルゴリズムの授業で学んだ以下の考えを思いついた.
整数は配列に格納されますが、値とインデックスは別々に保存されます.
  次に,本問題のメモリ制限が512 MBであることを見ると,この方式が正しい可能性があると予想できる.
  「インデックスを保持」
  インデックス保持の本能は,このような問題の入力範囲が非常に大きく,基本的なソートアルゴリズムが重複文に挿入されて使用できない場合に十分考慮できる考えである.問題の例を通して簡単に説明します.
以下にxが並んでいます.
value : 2 4 -10 4 -9
x_index : 0 1 2 3 4
このような状態にある.このとき,本題ではXiより小さい数のXj個をXiと記す.入力範囲が広い場合(重複する繰り返し文を使用する)、どのような方法が考えられますか?
  すなわち,配列はまず無折り畳み順に並べ替えられる.
value : -10 -9 2 4 4
  初期入力状態配列のインデックス値をx indexフィールド名として保持すると、次のようになります.
x_index : 2 4 0 1 3
(1と3は順序依存x)
  このソートステータスの配列で、インデックスを再作成します.
value : -10 -9 2 4 4
new_index : 0 1 2 3 4
はい.今、答えが現れ始めます.
そうですね.配列がソートされている場合、ソート状態の0からn-1インデックスは、この問題で検索するXi"の値を直接指します.
  しかし、このとき、上のように、一つ問題があります.ちょうどいい時だ.これは、単純な重複文の重複によって解決できます.もちろん,ここでの重複複文は理論的にはO(n^2)であるが,これらの入力は実際には考慮する必要はないので,あまり関係ない.
  今残っているのは並べ替えです.この場合、ソートの基準はvalueではなくx indexです.
value : 2 4 -10 4 -9
x_index : 0 1 2 3 4
new_index : 2 3 0 3 1
これで問題を解決できる.実際の解答では、new indexというフィールド名ではなくprime indexというフィールド名が使用されています.
  ちなみに、実施形態では、1つの鍵に関する様々な情報を保持するために、1つの構造体が必要である.また,アルゴリズムタイトルのsort関数を用いる場合,異なるソート基準に基づいて2回ソートすることが重要である.これは、次のコードで技術を検証することができます.return typeがboolの比較関数を作成するだけです.異なる標準フィールドを設定します.
  次はコードです.

#include <iostream>
#include <algorithm>
// BOJ - 18870 Coordinates Compression
using namespace std;

typedef struct {
	int value;
	int x_index;
	int prime_index;
}Coord;

Coord x[1000000];

bool pred_value(Coord a, Coord b) {
	if (a.value < b.value) return true;
	return false;
}

bool pred_x_index(Coord a, Coord b) {
	if (a.x_index < b.x_index) return true;
	return false;
}

int main(void) {
	int n, cnt = 0;
	Coord newItem;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> newItem.value; newItem.x_index = i;
		x[i] = newItem;
	}

	sort(x, x + n, pred_value);

	for (int i = 0; i < n; ) {
		x[i].prime_index = cnt;
		int j = i + 1;
		for ( ; x[j].value == x[i].value; j++)
			x[j].prime_index = cnt;
		i = j;
		cnt++;
	}

	sort(x, x + n, pred_x_index);

	for (int i = 0; i < n; i++) 
		cout << x[i].prime_index << ' ';

	return 0;
}