c++演算法之離散化

什麼是離散化？

　　離散化，故離散數學，其中的“離散”就是不連續的意思。離散化可以保持原數值之間相對大小關係不變的情況下將其映射成正整數。

也就是給可能用到的數值按大小關係分配一個編號，來代替原數值進行各種操作。

離散化步驟：

1.排序

2.去重

3.歸位

舉一個例子：

將{4000，201,11,45,830}離散為{5,4,3,2,1}：

1     4000 201 11 45 830
2        1      2   3  4  5
3      sort:
4 離散  11 45 201 830 4000
5        3      4  2   5    1
6 編號      1   2  3   4    5
7                   
8 a[1~n]:[5]  [3] [1] [2]  [4]

既然講了這麼多，是時候上代碼了：

1.去重離散

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[101100],b[101100];
 5 int main(){
 6     int n;
 7     cin >> n;
 8     for(int i=1;i<=n;i++){
 9         cin >> a[i];//未排序 
10         b[i]=a[i];//副本 
11     }
12     sort(b+1,b+n+1);
13     int cnt=unique(b+1,b+n+1)-(b+1);//去重函數unique
14     for(int i=1;i<=n;i++){
15         //二分查找函數lower_bound():>=a[i]的地址，“-b”就可以返回編號
　　　　　　//這裡註意：減去的b可不是b的數值，是b的地址 
16         a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
17         printf("%d ",a[i]);
18     } 
19     return 0;
20 }

2.不去重離散

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[101100],b[101100]
 5 int main(){
 6     int n;
 7     cin >> n;
 8     for(int i=1;i<=n;i++){
 9         cin >> a[i].x;//未排序 
10         a[i].y=a[i].x;//副本 
11     }
12     sort(b+1,b+n+1);
13     for(int i=1;i<=n;i++){
14         //二分查找函數:>=a[i]的地址，“-b”就可以返回編號 
15         a[i]=lower_bound(b+1,b+n+1,a[i])-b;
16         printf("%d ",a[i]);
17     } 
18     return 0;
19 }

不過，我個人覺得不去重的離散好寫，因為不用那個噁心人的unitque。