基础思维——离散化（附例题）

谁践踏了优雅 2022-12-13 04:48 92阅读 0赞

#### 引论 ####

> 离散化：  
> 把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。具体来说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。  
> –  
> 例如：  
> 原数据：1,999,100000000000,15；处理后：1,3,4,2；  
> 原数据：\{100,200\}，\{20,50000\}，\{1,400\}；  
> 处理后：\{3,4\}，\{2,6\}，\{1,5\}；  
> –  
> 例如：  
> 在一个坐标轴很长(>1e8)，给你1e4个坐标，询问某一个点，坐标比它小的点有多少。我们只需要知道他们之间的相对大小就可以，这就需要离散化。

#### 两种离散化方法（去重与不去重） ####

##### 1、离散化——去重 #####

**理解思路**  
①、在 book 数组中记录出现的元素大小 tot。  
②、对 book 数组进行从小到大排序，利用 unique函数对 book 数组进行去重，得到去重后的数组大小 c 。

//unique(book,book+n);
    //前一个是当序列的相邻的数据相同时，删除相邻相同的数字。
    sort(book, book+tot);
    //必须先排序
    int c = unique(book, book+tot) - book;

③、再对 book 数组进行从小到大排序，在 book 数组下找原数组 num 对应的下标即为离散数组 ans。

for (int i=0; i<n; i++) { 
        ans[i] = lower_bound(book, book+c, num[i])-book;
    }

--------------------

离散化——去重：整合代码

#include<bits/stdc++.h>
    using namespace std;
    int ans[100010]={ 0};//离散化后数组
    int num[100010], book[100010];
    int n;
    
    int main(){ 
    	int n;
    	scanf("%d", &n);
    	for (int i=0; i<n; i++) { 
    	    scanf("%d",&num[i]);
    	    book[i] = num[i];
    	}
    	 
    	int c = unique(book, book+n) - book;
    	sort(book , book+c);
    	 
    	for (int i=0; i<n; i++) { 
    	    ans[i] = lower_bound(book, book+c, num[i])-book;
    	}
    	for(int i=0; i<n; i++){ 
    		printf("%d ", ans[i]);
    	}
    	
    	return 0;
    }

##### 2、离散化——不去重 #####

**理解思路**  
①、利用结构体数组 num 存储每个元素对应的值 data 及下标 id。  
②、将 结构体数组 num 按 data 从小到大排列。  
③、利用 num 每个元素下标 id 唯一性的特点，生成相应的离散化 ans 数组。

//自认为这一步很妙
    for (int i=0; i<n; i++) { 
        ans[num[i].id] = i;
    }

--------------------

离散化——不去重：整合代码

#include<bits/stdc++.h>
    using namespace std;
    int ans[100010]={ 0};//离散化后数组
    int n;
     
    struct node { 
        int data , id;
    }num[100010];
    
    bool cmp(node a, node b){ 
    	return a.data<b.data;
    }
    
    int main(){ 
    	int n;
    	scanf("%d", &n);
    	for (int i=0; i<n; i++) { 
    	    scanf("%d",&num[i].data);
    	    num[i].id = i;
    	}
    	 
    	sort(num , num+n, cmp);
    	 
    	for (int i=0; i<n; i++) { 
    	    ans[num[i].id] = i;
    	}
    	for(int i=0; i<n; i++){ 
    		printf("%d ", ans[i]);
    	}
    	
    	return 0;
    }

--------------------

#### 例题 ####

**程序自动分析** [题目链接][Link 1]  
![题目1][1]  
![题目2][2]  
![题目2][2 1]  
![题目3][3]  
大概题意：有 t 组需要判定的问题，每组问题有 n 个限制条件，每个条件格式为：i j e。由 e 决定限制内容，例如当 e = 1时，i = j。当 e = 0 时， i != j。若当前判定的问题能够满足 n 个限制条件，则输出"YES"，否则输出"NO"。

ps：数据范围 1 <= n <= 106, 1 <= i, j <= 109

--------------------

**解题思路**  
①、由于1 <= i, j <= 109的数据范围过大，若直接用数组存储数据空间复杂度过大，另外判定问题的标为条件是否成立，所以我们需要 **去重离散化记录数据** 。  
②、得到离散化数组后，运用并查集、递归缩短路径。

//递归缩短路径: 妙
    int get(int a){ 
    	if(u[a]==a) return a;
    	return u[a] = get(u[a]);
    }

为了更清晰的判定问题是否成立，首先进行 e=1 的条件，再判定 e=1的条件是否成立。若成立则输出"YES"，否则输出"NO"。

--------------------

整合代码

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll book[2000010];
    int u[1000010]; 
    
    struct node{ 
      ll x, y, e;
    }a[1000010];
    
    bool cmp(node a, node b){ 
      return a.e>b.e;
    }
    
    //递归缩短路径
    int get(int a){ 
      if(u[a]==a) return a;
      return u[a] = get(u[a]);
    }
    
    int main(){ 
      int t;
      scanf("%d", &t);
      
      while(t--){ 
      	int n, tot=0;
      	scanf("%d", &n);
      	for(int i=0; i<n; i++){ 
      		scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].e);
      		book[tot++] = a[i].x;
      		book[tot++] = a[i].y;
      	}
      	
      	sort(book, book+tot);
      	//统计去重后的元素个数 
      	int c = unique(book,book+tot) - book;
      	//给每个元素从大到小编号 
      	for(int i=0; i<n; i++){ 
      		a[i].x = lower_bound(book, book+c, a[i].x)-book;
      		a[i].y = lower_bound(book, book+c, a[i].y)-book;
      	}
      	
      	sort(a, a+n, cmp);
      	for(int i=0; i<c; i++)
      		u[i] = i;
      	
      	int flag=1;
      	for(int i=0; i<n; i++){ 
      		int dy = get(a[i].y);
      		int dx = get(a[i].x);
      		if(a[i].e){ 
      			u[dx] = dy;
      		}
      		else{ 
      			if(u[dx]==u[dy]){ 
      				flag=0;
      				printf("NO\n");
      				break;
      			}
      		}
      	}
      	if(flag) 
      		printf("YES\n");
      }	
      
      return 0;
    }

#### 总结 ####

离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。要掌握这个思想，必须从大量的题目中理解此方法的特点。例如，在建造线段树空间不够的情况下，可以考虑离散化。

[Link 1]: https://www.luogu.com.cn/problem/P1955
[1]: /images/20221123/d1877ce03e294f7c91e01295fb29ee51.png
[2]: /images/20221123/ee1f5fbd774f4e2caef922d4b8989194.png
[2 1]: /images/20221123/a42351266a984be08204c6b60567b102.png
[3]: /images/20221123/70d1e278ab7f4863b63548db7afd80c9.png