CF379C.New Year Ratings Change

普及/提高-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 a__i 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.

一个非常著名的互联网资源网站(我们称之为 X 站)推出了一项新年冒险活动。具体而言,他们决定为所有访问者评定等级。

该网站共有 nn 位用户,对于每位用户,我们已知其希望在新年礼物中获得的等级值。已知第 ii 位用户希望至少获得 aia_i 个等级单位作为礼物。

X 站由一群极具创造力且精打细算的管理员运营。一方面,他们希望所给出的等级互不相同;另一方面,礼物中所有等级的总和必须尽可能小。

请帮助 X 站完成这一富有挑战性的等级分配任务,找出最优的分配方案。

输入格式

The first line contains integer n (1 ≤ n ≤ 3·105) — the number of users on the site. The next line contains integer sequence _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109).

第一行包含一个整数 nn(1 ≤ n ≤ 3⋅1051 \leq n \leq 3\cdot10^5)—— 网站上的用户数量。
下一行包含一个整数序列 a1, a2, ..., ana_1, a_2, ..., a_n(1 ≤ ai ≤ 1091 \leq a_i \leq 10^9)。

输出格式

Print a sequence of integers _b_1, _b_2, ..., b__n. Number b__i means that user i gets b__i of rating as a present. The printed sequence must meet the problem conditions.

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

输出一个整数序列 b1, b2, …, bnb_1,\ b_2,\ \dots,\ b_n。其中,数字 bib_i 表示用户 ii 将获得 bib_i 单位的评分为礼物。所输出的序列必须满足题目的所有条件。

若存在多个最优解,输出其中任意一个即可。

输入输出样例

  • 输入#1

    3
    5 1 1

    输出#1

    5 1 2
  • 输入#2

    1
    1000000000

    输出#2

    1000000000

输入解题思路,AI测评打分。不知道怎么写?

首页