给出一列数字，在有些情况下，这些数字的值的绝对大小不重要，而相对大小很重要。如班级的分数有99 98 97 95 96，排名为 1 2 3 5 4。
离散化是一种数据处理的技巧，它把分布广而稀疏的数据转换位密集分布，从而能够让算法更快速、更省空间地处理。
离散化地步骤：排序，离散化，归位。
如： 4000 210 11 45 800
数组下标为 1 2 3 4 5
将它们存储在结构体中，在进行排序。
---------------------
排序： 11 45 210 800 4000
3 4 2 5 1
------------------------
离散化： 1 2 3 4 5
数组的下标：3 4 2 5 1
----------------------
归位 ： 5 3 1 2 4
数组下标 1 2 3 4 5
下面是代码解析：
#define _CRT_SECURE_NO_WARNINGS 1
//离散化
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
struct data1 {int val;int id; // 用坐标代替
}olda[N];
int newa[N];
bool cmp(data1 x, data1 y) { return x.val < y.val; }
int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &olda[i].val);olda[i].id = i;}sort(olda + 1, olda + 1 + n, cmp); //排序//离散化 + 归位 for (int i = 1; i <= n; i++) {newa[olda[i].id] = i;if (olda[i].val == olda[i - 1].val)newa[olda[i].id] = newa[olda[i - 1].id];}for (int i = 1; i <= n; i++)printf("%d", newa[i]);return 0;
}用STL函数实现离散化：
lower_bound() 和 unique()函数实现离散化。
查找第1个等于或大于x的元素：lower_bound()且等于x。位置如 pos = lower_bound(a,a+n,x) - a。
unique()函数：
unique是 c++标准模板库STL中十分实用的函数之一，使用此函数需要#include <algorithm>头文件
该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素
(1) 这里的去除并非真正意义的erase，而是将重复的元素放到容器的末尾，返回值是去重之后的尾地址。
注意这一点：它只对相邻的元素。
(2) unique针对的是相邻元素，所以对于顺序错乱的数组成员，或者容器成员，需要先进行排序，可以调用std::sort()函数。
#define _CRT_SECURE_NO_WARNINGS 1
//离散化
#include<bits/stdc++.h>
using namespace std;
const int N = 5000010;
int olda[N];
int newa[N];
int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &olda[i]);newa[i] = olda[i]; //这一步很关键}sort(olda + 1, olda + n + 1);//默认是从小到大 less<int>()int cnt = n; // 记录个数 调用unique函数时，是去重的数组//cnt = unique(olda + 1, olda + 1 + n) - (olda + 1);//返回不重复的尾元素 如 1 1 2 3 调用函数后 1 2 3 1 返回 3 for (int i = 1; i <= cnt; i++) {newa[i] = lower_bound(olda + 1, olda + 1 + n, newa[i]) - olda;}for (int i = 1; i <= cnt; i++) {printf("%d ", newa[i]);}return 0;
}
