[技巧] 离散化

离散化

离散化作为一种常见的技巧,可以有效地降低时间和空间复杂度.本文介绍两种离散化模板.此外,离散化有一些坑点,在处理染色问题的端点方面不能直接套用模板.这种题应该具体分析.

方法一: 缺点:效率略低,未保存原数据 优点:重复元素离散值相同

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e1+5;
int t[N],a[N];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
        t[i] = a[i];
    }

    sort(t+1,t+1+n);
    int m = unique(t+1,t+1+n)-t-1; // 最大离散数
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(t+1,t+m+1,a[i])-t;
    }
    return 0;
}

方法二:

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
struct Node{
    int v,id;
    bool operator < (const Node a)const{
        return v<a.v;
    }
};

int n;
int t[N];
Node a[N];
int main(){
    scanf("%d",&n);
    for(int i=1; i <= n; i++){
        scanf("%d",&a[i].v);
        a[i].id = i;
    }
    sort(a+1,a+n+1);
    for(int i = 1; i <= n; i++){
  	    t[a[i].id] = i;
    }
    return 0;
}