[18870]座標圧縮
[18870]座標圧縮
質問する
垂直線上のN個の座標X 1,X 2,...,XNがあります.この座標に座標圧縮を適用します.
Xiを座標圧縮した後、X'iの値はXi>Xjを満たす異なる座標の個数に等しくなければならない.
X1, X2, ..., XNに座標圧縮を適用すると、X"1,X"2,...,X'Nを印刷します.
入力
1行目はNです.
2行目は、スペースで区切られたX 1、X 2、…、XNをあげます.
しゅつりょく
1行目X「1,X」2,...,X'Nをスペース出力に分割します.
制限
1 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109
コード#コード#
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
/* 빠른 cin cout */
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
/* 입력 */
int N;
cin >> N;
vector<int> input, position;
/* 풀이 */
int tmp;
for(int i = 0; i < N; i++) {
cin >> tmp;
input.push_back(tmp);
position.push_back(tmp);
}
sort(position.begin(), position.end());
position.erase(unique(position.begin(), position.end()), position.end());
/* 출력 */
for(int i = 0; i < N; i++) {
cout << lower_bound(position.begin(), position.end(), input[i]) - position.begin() << ' ';
}
}追加の説明
positionというベクトルを並べ替えて重複を解消する2つのベクトルが作成されました.
各入力に対して下限を使用します.位置に見つかったインデックスは0から始まる順序と同じなので、インデックスの出力が必要です.
Reference
この問題について([18870]座標圧縮), 我々は、より多くの情報をここで見つけました https://velog.io/@kkoala/18870-좌표-압축テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol