離散化思想

• 2020 年 11 月 1 日
• 筆記
• 演算法

離散化

離散化適合在數據範圍很大但是又只使用部分數據的時候使用

例題 ： AcWing 103

離散化函數：

sort(a, a + n);
for(int i = 0; i < n; i ++ ) {
    if(i == 0 || a[i] != a[i-1]) {
        b[m++] = a[i];
    }
}
//排序後進行離散化
int query (int x) {
	return low_bound(b, b + m, x) - b;
}
//查找數據映射到哪個整數上了

離散化概念：

離散化，把無限空間中有限的個體映射到有限的空間中去，以此提高演算法的時空效率。

通俗的說，離散化是在不改變數據相對大小的條件下，對數據進行相應的縮小。例如：

原數據：1,999,100000,15；處理後：1,3,4,2；

原數據：{100,200}，{20,50000}，{1,400}；

處理後：{3,4}，{2,6}，{1,5}；

​ — 來自 《百度百科》

簡單的來說就是一個把元素映射的過程，以減小數據範圍，方便進行計算。

常用在不關注數據本身的題目

小技巧：

//簡便的for循環
#define _for(i, a, b) for(int i = (a); i < (b); i ++ )
#define _rep(i, a, b) for(int i = (a); i <= (b); i ++ )

//sort的cmp函數
struct movie {
    int first, second;
}
bool cmp(movie m1, movoie m2) {
    if(m1.first == m2.first) return m1.second > m2.second;
    return m1.first > m2.first;
}