离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。 通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如： 原数据：1,999,100000,15；处理后：1,3,4,2； 原数据：{100,200}，{20,50000}，{1,400}； 处理后：{3,4}，{2,6}，{1,5}；
#include <iostream>#include <vector>#include <algorithm>using namespace std;//将node数组中的x和y坐标离散化,传入的值是其方向代表的最小值，一般都传入1//按照x从小到大，相同的x按照y值从小到大排序typedef struct node{ int x,y;}node;bool cmpx(node x,node y){ if(x.x<y.x) return true; else if(x.x>y.x) return false; else{ if(x.y<y.y) return true; else return false; }}//按照y值从小到大，相同的y按照x值从小到大排序bool cmpy(node x,node y){ if(x.y<y.y) return true; else if(x.y>y.y) return false; else{ if(x.x<y.x) return true; else return false; }}void lisanhua(node a[],int n,int &maxx,int &maxy){ int nowloc=0,lastloc=0; sort(a,a+n,cmpx);//按照x从小到大到y从小到大排序 while(lastloc < n){ nowloc = lastloc; while(lastloc < n && a[lastloc].x==a[nowloc].x) lastloc++; for(int i=nowloc;i<lastloc;i++) a[i].x=maxx; maxx++; } nowloc=0;lastloc=0; sort(a,a+n,cmpy); while(lastloc < n){ nowloc = lastloc; while(lastloc < n && a[lastloc].y==a[nowloc].y) lastloc++; for(int i=nowloc;i<lastloc;i++) a[i].y=maxy; maxy++; } //如果传入(a,1,1)得到的x的范围为[1,maxx),y的范围为[1,maxy)}int main(){ int n,maxx=1,maxy=1; node a[10]; cin >> n; for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y); lisanhua(a,n,maxx,maxy); for(int i=0;i<n;i++) cout << a[i].x << " " << a[i].y << endl; return 0;}新闻热点
疑难解答
