离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。 通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。 —百度百科
经常遇到二维坐标分不大，但数据量少，即稀疏的二维坐标的题。 例P3431 [POI2005]AUT-The Bus 一个二维坐标，x 轴的取值为[1, 1e9]， y 轴的取值为[1, 1e9]， 但数据只有 k（<=5000） 这1e9 * 1e9的图有用的点，最大为 5000，我们也建不了1e9 * 1e9的二维坐标，且程序运行时间大幅上升 这时候就需要对其进行离散化
就是对较大的坐标值，我们用较小的值来描述该点，也能够表示处理前各点之间的关系 用实例来描述该方法，对（5， 5000），（901， 300），（900， 6）， 进行离散化
对 x 轴离散化：先对 x 轴的点去重排序得到 5，900，901：5 -> 1，因为 5 与 900 不相邻，则900 -> 3，900 与 901 相邻，则901 -> 4 5, 900, 901 --> 1, 3, 4。依旧保留了之前相邻的关系
对 y 轴离散化：先对 y 轴的点去重排序得到 6， 300， 5000：6 -> 1, 因为6 与 300 不相邻，则300 -> 3,300 与 5000不相邻，则 5000 -> 5 6， 300， 5000 --> 1, 3, 5 最后离散后得到的点为 （1，5），（4，3 ），（3，1）
代码实现：
#include <bits/stdc++.h> using namespace std; const int maxn = 1e3; int n, m, k, ans; int x[maxn], y[maxn]; int nx[maxn*2], ny[maxn*2]; int tot1 = 1, tot2 = 1; int mp[maxn*2][maxn*2]; struct node { int x, y; }a[maxn]; int main(){ cin >> n >> m >> k; for(int i = 0; i < k; i++){ cin >> x[i] >> y[i]; a[i].x = x[i], a[i].y = y[i]; } // 排序 sort(x , x + k); sort(y, y + k); // 去重 并得到有多少个点 int len1 = unique(x , x + k) - x; int len2 = unique(y , y + k) - y; // 离散化 x 轴 for(int i = 0; i < len1; i++){ if(i && x[i] != x[i - 1] + 1) nx[tot1++] = x[i] - 1, nx[tot1++] = x[i]; else nx[tot1++] = x[i]; } for(int i = 0; i < tot1; i++) cout << nx[i] << " "; cout << endl; // 离散化 y 轴 for(int i = 0; i < len2; i++){ if(i && y[i] != y[i - 1] + 1) ny[tot2++] = y[i] - 1, ny[tot2++] = y[i]; else ny[tot2++] = y[i]; } // for(int i = 0; i < k; i++){ int newx = lower_bound(nx, nx + tot1, a[i].x) - nx; int newy = lower_bound(ny, ny + tot2, a[i].y) - ny; mp[newx][newy] = 1; } for(int i = 1; i < tot1; i++){ for(int j = 1; j < tot2; j++) cout << mp[i][j] << " "; cout << endl; } return 0; }