离散化模板题 I ——重复元素离散化后的数字相同

题目描述

现有数列A1, A2, ⋯, An，数列中可能有重复元素。
现在要求输出该数列的离散化数列，重复元素离散化后的数字相同。

输入

第一行，一个整数 n。
第二行，n 个整数整数A1, A2, ⋯, An。

输出

一行，包括 n 整数。表示数列对应的离散化数列，重复元素离散化后的数字相同。

样例输入

6

1 23424 242 65466 242 0

样例输出

1 3 2 4 2 0

提示

【数据范围】
对于 50% 的数据，1 ≤N ≤ 103。
对于 100% 的数据，1 ≤ N ≤ 105, -109 ≤ Ai≤ 109。

代码：

#include <bits/stdc++.h>

using namespace std;

int main(){

    int n;

    cin>>n;

    int*arr = new int[n];

    int*carr = new int[n];

    for (int i = 0; i < n; i++){

        cin>>arr[i];

        carr[i]=arr[i];

    }

    sort(arr,arr+n);

    int m =unique(arr,arr+n)-arr;

    for (int i = 0; i < n; i++){

       carr[i]=lower_bound(arr,arr+m,carr[i])-arr;

    }

    for (int i = 0; i < n; i++){

       cout<<carr[i]<<" ";

    }

}

巴特西

离散化模板题 I ——重复元素离散化后的数字相同

离散化模板题 I ——重复元素离散化后的数字相同

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章