离散化

有些数据很大无法作为数组的下标，这个问题已经让我碰到过许多次了，现在来整理一下离散化

离散化

离散化是指一些数据只需要知道它们之间的相对大小，与本身的大小的多少无关
如：对99999999，99999，1，23453，888892这五个数字，数据之间相差较大，且对于第一个数字用数组也无法用下标表示，所以就要将数组离散化，需要相对大小就可。这五个数字离散后为5，3，1，2，4

对重复元素进行离散化

代码一：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 100005

int main() 
{
	int a[N],b[N];
	int n;
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b,b+n);
	int m =unique(b,b+n)-b;
	for(i=0;i<n;i++)
	{
		a[i]=lower_bound(b,b+m,a[i])-b;
	}
	for(i=0;i<n;i++)
	printf("%d ",a[i]);
	printf("\n");
	return 0;   
}

这个代码对上面五个数字进行离散化后的结果是4，2，0，1，3

代码二：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 100005

int main() 
{
	int a[N],b[N];
	int n;
	int i;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b,b+n);
	int m =unique(b,b+n)-b;
	for(i=0;i<n;i++)
	{
		a[i]=upper_bound(b,b+m,a[i])-b;//二分区间是去重后的区间
	}
	for(i=0;i<n;i++)
	printf("%d ",a[i]);
	printf("\n");
	return 0;   
}

这个代码所得到的结果是5，3，1，2，4

区别：使用的二分函数不同

unique是“去掉”容器中相邻的重复元素（不一定要求数组有序），这里的去掉是将重复元素添加到容器的末尾（因此数组大小没有改变），返回的是去重后的尾地址。想要得到去重后的数组大小，就需要减去初始地址。

对无重复元素进行离散化

这种方法是用结构体储存原来元素的位置，排序之后重新赋值，

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 100005
struct node{
	int val,id;
	/*bool operator<(const node &a) const{
		return val<a.val;
		}*/				//作用与cmp排序一样 
}a[N];
int cmp(node a,node b)
{
	return a.val<b.val;
}
int main() 
{
	int b[N];
	int n;
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	for(i=1;i<=n;i++)
	{
		b[a[i].id]=i;
	}
	for(i=1;i<=n;i++)
	printf("%d ",a[i]);
	printf("\n");
	return 0;   
}

在这段代码中，结构体中有段注释部分的作用与我写的cmp函数一样，为什么要在结构体中写成那样目前我也不太明白。
样例：
INPUT
5
9999 999 99 9 1
输出
1 9 99 999 9999
由两种输入与输出的结果看，就可以看出两种离散化的不同了。

样例

西安邮电大学第五届ACM-ICPC校赛（同步赛）——G题——校车

• 题目描述
  西安邮电大学有一辆从老校区到新校区的校车，总共有 n 个学生乘坐校车，在ai站上车，在bi站下车。学校打算去除一部分不必要的站点，请问需要保留多少站点，需要安排多少个座位？
• 输入描述
  输入 T 组数据 (1≤T≤10)
  输入 n (1≤n≤1e5)
  输入 n 组 ai,bi(1 ≤ ai < bi ≤ 1e9)
• 输出描述
  输出保留站点数，座位数。
• 示例一：
  输入：
  1
  3
  1 2
  1 3
  2 4
  输出：
  4 2
• 解题思路
  把输入的站点排序离散化得出站点数，然后利用离散后的相对大小，去求站数的上车人数和下车人数。
• 解体代码

  #include<stdio.h>
  #include<iostream>
  #include<algorithm>
  #include<string.h>
  using namespace std;
  struct node{
  	long long x,y;
  }a[100005];
  long long b[200005];//离散后数组
  long long c[100005]; 
  int cmp(node a,node b)
  {
  	return a.x<b.x;
  }
  int main()
  {
      int t;
  	int n,i,j;
  	scanf("%d",&t);
  	while(t--)
  	{
  		int cnt=0;
  		scanf("%d",&n);
  		for(i=0;i<n;i++)
  		{
  			scanf("%lld%lld",&a[i].x,&a[i].y);
  			b[cnt++]=a[i].x;
  			b[cnt++]=a[i].y;
  		}
  		sort(a,a+n,cmp);
  		sort(b,b+cnt);
  		cnt=unique(b,b+cnt)-b;//离散后的数组大小 
  		memset(c,0,sizeof(c));
  		int sum=1,ans=1;
  		int h;
  		h=lower_bound(b,b+cnt,a[0].y)-b+1;//把c的下标从1开始表示，表示第一站 
  		c[h]++;
  		for(i=1;i<n;i++)
  		{
  			if(a[i].x==a[i-1].x)
  			{
  				ans++;
  				h=lower_bound(b,b+cnt,a[i].y)-b+1;
  				c[h]++; 
  			}
  			else
  			{
  				h=lower_bound(b,b+cnt,a[i].x)-b+1;
  				ans++;
  				for(j=1;j<=h;j++)//该出站的人 
  				{
  					ans=ans-c[j];
  					c[j]=0; 
  				}
  				h=lower_bound(b,b+cnt,a[i].y)-b+1;
  				c[h]++;
  			}
  			sum=max(sum,ans);
  		} 
  		printf("%d %d\n",cnt,sum);
  	} 
  	return 0;
  }