一、离散化是一种工具，可以优化时间空间复杂度。
二、基本思想：在众多可能的情况中只考虑我需要的值。
三、使用的情况：
（1）
将连续的变量变成一个个的值，变成离散的变量，这个过程也就是所谓的离散化。
如UVA10173
题意：在平面内用最小的矩形覆盖平面内所有的点。
这个问题不好处理 因为我们不知道矩形到底倾斜多少度。但是矩形的每条边一定有1个点。
可以想象平面内四条边像点的方向逼近，当穿过点时停止。
方法可行，但是矩形的倾斜角是个实数无法枚举。
我们又考虑，矩形至少有1条边经过连个两个点，所以我们计算出两两点的斜率进行枚举。将实数分解为一个一个的整数。
（2）
数据已经是一个个整数了，但范围极大，我们想方法缩小规模。
如： 100000 10000000000 100000000000000000 10000000000000000000000000
这四个数字和 1 2 3 4个数字没有区别。
典型例题：矩形覆盖
四、使用步骤
（1）排序 去重 索引
（2）代码实现
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[100],newx[100],hashx[100]; int n,size; /*int lower_bound(int x) { int l=1,r=size,mid; while(l<=r) { mid=l+r>>1; if(a[mid]==x)return mid; if(a[mid]<x)l=mid+1; else r=mid-1; } }*/ int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); hashx[i]=a[i]; } sort(hashx+1,hashx+n+1); size=unique(hashx+1,hashx+n+1)-(hashx+1); for(int i=1;i<=n;i++) newx[i]=lower_bound(hashx+1,hashx+n+1,a[i])-hashx; printf("%d ",size);//排序去重后的数字个数。 for(int i=1;i<=n;i++) printf("%d ",newx[i]); printf(" "); for(int i=1;i<=size;i++)//知道离散化后的数求原数。 printf("%d ",a[newx[i]]); return 0; } /* 栗子1： 5 1 5 10 15 20 5//排序去重之后数的个数 1 2 3 4 5 1 5 10 15 20 */ /* 5 1 1 5 10 15 4 //两个1相同去重之后记为1个数。 1 1 2 3 4 1 1 1 5 */
参考：http://www.cnblogs.com/kevince/archive/2014/08/06/3893531.html
http://www.matrix67.com/blog/archives/108