離散化模闆:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000;
int a[maxn];
int b[maxn];
int n,m;
void lisan();
int main()
{
cin>>n;//元素個數
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
b[++m]=a[i];//b[]作為離散化的數組
}
lisan();
return 0;
}
void lisan() {
sort(b+1,b+1+m);//将b數組排序,因為是從b[1]開始存儲的,是以要b+1
m=unique(b+1,b+1+m)-b-1;//去重操作,傳回不同元素的個數
for(int i=1;i<=n;++i) {
a[i]=lower_bound(b+1,b+1+m,a[i])-b;
cout<<a[i]<<" ";
}
}
為什麼要離散化:
當以權值為下标的時候,值太大,存不下。
然後把要離散化的每一個數組裡面的數映射到另一個值小一點的數組裡面去。
法2: