New Year Ratings Change（贪心）

C. New Year Ratings Change

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

One very well-known internet resource site (let's call it X) has come up with a New Year adventure. Specifically, they decided to give ratings to all visitors.

There are n users on the site, for each user we know the rating value he wants to get as a New Year Present. We know that user i wants to get at least ai rating units as a present.

The X site is administered by very creative and thrifty people. On the one hand, they want to give distinct ratings and on the other hand, the total sum of the ratings in the present must be as small as possible.

Help site X cope with the challenging task of rating distribution. Find the optimal distribution.

Input

The first line contains integer n (1 ≤ n ≤ 3·105) — the number of users on the site. The next line contains integer sequencea1, a2, ..., an (1 ≤ ai ≤ 109).

Output

Print a sequence of integers b1, b2, ..., bn. Number bi means that user i gets bi of rating as a present. The printed sequence must meet the problem conditions.

If there are multiple optimal solutions, print any of them.

Sample test(s)

input

3
5 1 1

output

5 1 2

input

1
1000000000

output

1000000000

 

      题意：

      给一个数N（1到300000），代表有N个数，随后给出N个数。分别是 a1 到 an ，ai 范围是 1 到 10^9。分配数字要求必须满足：

      1.大于等于本身这个数；

      2.分配后得的这个数字必须不同于其他所有的数；

      3.分配所有数字后得出来的这些数的总和要求最小。

 

      思路：

      贪心。对 ai 进行由小到大排序，由小的值（并不是从原来的排序的顺序）开始重新赋值，更新的同时维护当前的最小值。

 

      AC：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef struct
{
    int val;  //当前值
    int num;  //当前值的序号
}node;
node no[300005];
int fin[300005];  //与当前值序号对应

int cmp(node a,node b)
{
    return a.val<b.val;   //由小到大排序
}

int main()
{
    int n,m = -1;
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&no[i].val);
        no[i].num = i;
    }
    sort(no + 1,no + 1 + n,cmp);
    for(int i = 1;i <= n;i++)
    {
        fin[no[i].num]=max(m+1,no[i].val);
        m=fin[no[i].num];
    }
    for(int i = 1;i <= n;i++)
    {
        printf("%d",fin[i]);
        i == n ? printf("\n") : printf(" ");
    }
    return 0;
}