陽気な妖姫 [いろはちゃんコンテスト Day2 C]

https://atcoder.jp/contests/iroha2019-day2/tasks/iroha2019_day2_c

前提知識

• 座標圧縮

解説

https://atcoder.jp/contests/iroha2019-day2/submissions/5214368

大小関係を維持したまま、配列の数字を変えて総和を最小化する問題。
これは座標圧縮をすればいい。
通称、座圧であるが、この概念自体を知っていれば、この問題はそんなに難しくない。
（知らないと実装とか難しいかも）
1-indexedにする必要があるので注意。

int N, H[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> H[i];
 
	vector<int> dic;
	rep(i, 0, N) dic.push_back(H[i]);
	sort(all(dic));
	dic.erase(unique(all(dic)), dic.end());
 
	rep(i, 0, N) H[i] = lower_bound(all(dic), H[i]) - dic.begin() + 1;
	rep(i, 0, N) printf("%d\n", H[i]);
}