数据离散化

1.5.4 人物风云榜

Description

又到了云之国一年一度的任务风云榜更新的大日子了。
给出每个人风云力数值，需要你给出每个人的排名。注意，排名存在并列的情况。

Input

一共有 222 行。
第一行一个整数 nnn ，表示一共有 nnn 个人。
第二行有nnn个空格隔开的整数。第iii个数aia_iai​表示第iii个人的风云力数值。

Output

输出仅一行，共n个整数，第iii个数ai表示第i个人的风云榜排名。

Sample Input 1

5
50 40 30 100 50

Sample Output 1

2 4 5 1 2 

Hint

50%的数据 1≤n≤60001 \leq n \leq 60001≤n≤6000.
100%的数据 1≤n≤105;0&lt;ai&lt;2311 \leq n \leq 10^5;\quad 0 &lt; a_i &lt; 2^{31}1≤n≤105;0<ai​<231.

Source

Saikr Online Judge http://oj.saikr.com

 离散化，将原始数据的序号pos保存下来，再将值进行排序，然后开一个新的数组来记录原始序列
    的大小编号，将原始序列的pos值作为结果数组的下标，将排好序的数组的下标作为结果数组的值。这就能实现原始序列的排序。

/**
    离散化，将原始数据的序号pos保存下来，再将值进行排序，然后开一个新的数组来记录原始序列
    的大小编号，将原始序列的pos值作为结果数组的下标，将排好序的数组的下标作为结果数组的值。
    这就能实现原始序列的排序。
*/
 
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Node
{
    int val,pos;
};
bool cmp(Node a,Node b)
{
    if(a.val!=b.val)
        return a.val > b.val;
    return a.pos < b.pos;
}
int main()
{
    int n;
    scanf("%d",&n);
    Node a[n+1];
    int result[n+1];
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i].val);
        a[i].pos=i;
    }
 
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        if(i>1&&a[i].val==a[i-1].val)
            result[a[i].pos]=i-1;
        else
            result[a[i].pos]=i;
    }
    for(int i=1;i<=n;++i)
    {
        if(i==1)
            printf("%d",result[i]);
        else
            printf(" %d",result[i]);
    }
    return 0;
}

在来一题：

1.5.5 点的离散化

Description

在平面直角坐标系上有nnn个整点(xi,yi)(x_i,y_i)(xi​,yi​).现在需要你按照从左往右，从下往上的顺序依次给每个点编号111到nnn。
要求按照编号从小到大的顺序输出每个点的坐标；并按照点的输入顺序输出每个点的编号。

Input

第一行一个正整数nnn。表示点的个数。
接下来有nnn行。第i+1i+1i+1行有两个以空格分隔的整数xi&ThickSpace;yix_i \; y_ixi​yi​。

Output

共n+1n+1n+1行。前nnn行分别是点的坐标，第iii行两个以空格分隔的数Xi&ThickSpace;YiX_i\; Y_iXi​Yi​,表示编号为iii的点的坐标。
第n+1n+1n+1行，共nnn个以空格分隔开的整数。第iii个数rir_iri​表示输入中第iii个点的编号。

Sample Input 1

4
0 0
1 1
0 3
3 0

Sample Output 1

0 0
0 3
1 1
3 0
1 3 2 4

Hint

∣xi∣,∣yi∣≤231−1;1≤n≤106.|x_i|,|y_i| \leq 2^{31}-1; 1 \leq n \leq 10^6.∣xi​∣,∣yi​∣≤231−1;1≤n≤106.

Source

Saikr Online Judge http://oj.saikr.com

/**
    离散化，将原始数据的序号pos保存下来，再将值进行排序，然后开一个新的数组来记录原始序列
    的大小编号，将原始序列的pos值作为结果数组的下标，将排好序的数组的下标作为结果数组的值。
    这就能实现原始序列的排序。
*/
 
#include <iostream>
#include <algorithm>
using namespace std;
struct Node
{
    int x,y,pos;
};
bool cmp(Node a,Node b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    if(a.y!=b.y)
        return a.y<b.y;
    return a.pos<b.pos;
}
 
int main()
{
    int n;
    scanf("%d",&n);
    Node point[n+1];
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&point[i].x,&point[i].y);
        point[i].pos=i;
    }
 
    int result[n+1];
    sort(point+1,point+n+1,cmp);
    for(int i=1;i<=n;++i)
    {
        result[point[i].pos]=i;
    }
 
    for(int i=1;i<=n;++i)
        printf("%d %d\n",point[i].x,point[i].y);
    for(int i=1;i<=n;++i)
        printf("%d ",result[i]);
    return 0;
}