离散化 模板 2种写法
样例
输入：
6 1000000 999 88 1 10 6666
输出：
6 4 3 1 2 5
//离散化的2种写法 //常规写法，排序+结构体+数组 #include <cstdio> #include <algorithm> #define maxn 100100 using namespace std; struct node{ int seq,v; }a[maxn]; int b[maxn],n; int cmp(node a,node b){ return a.v==b.v?a.seq<b.seq:a.v<b.v; } int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i].v),a[i].seq=i; sort(a+1,a+1+n,cmp); for(i=1;i<=n;i++)b[a[i].seq]=i; for(i=1;i<=n;i++)printf("%d ",b[i]); return 0; }
//离散化的2种写法 //信奥写法，源自 第二十届(NOIP2014)四、阅读程序写结果3. 详见https://blog.csdn.net/mrcrack/article/details/53954758 //排序+数组 #include <cstdio> #include <algorithm> #define maxn 100100 using namespace std; int a[maxn],ind[maxn],rank[maxn],n;//请注意ind[]是中介。 int cmp(int x,int y){ return a[x]<a[y]; } int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&a[i]),ind[i]=i;//位次第i位的,在原序列中是第ind[i]位。 sort(ind+1,ind+1+n,cmp); for(i=1;i<=n;i++)rank[ind[i]]=i; for(i=1;i<=n;i++)printf("%d ",rank[i]);//rank[i]原序列中第i位，经离散化后，数值是rank[i]. return 0; }
