Algoogle

Algorithm for Programming Contest

座標圧縮

基本情報


計算量 初期化 , 圧縮 , 展開
用途 座標を圧縮する

N := 圧縮する座標の数

解説


入力の個数に対して考えられる座標の範囲が広い時, 座標の大小関係を維持しつつ値の範囲を狭める.
コードではzipで圧縮後の座標, unzipで圧縮前の座標を受け取る.

コード


(compress.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
map<int,int> zip;
int unzip[MAP];

int compress(vector<int> &x) {
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(),x.end()),x.end());
    for(int i = 0; i < x.size(); i++){
        zip[x[i]] = i;
        unzip[i] = x[i];
    }
    return x.size();
}

問題


Comments