No.2304 Distinct Elements
タグ : / 解いたユーザー数 43
作問者 :
Shirotsume
/ テスター :
👑 
hamamu
ygussany
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$. You may perform the following operation on this sequence any number of times.
- Choose an integer $i$ satisfying $1 \leq i \leq N$. Replace $A_i$ with either $A_i + 1$ or $A_i - 1$, whichever you like.
Your goal is to reach a state where $A_i \neq A_j$ for every pair of integers $(i, j)$ satisfying $1 \leq i \lt j \leq N$. Find the minimum number of operations required to do so.
Constraints
- All input values are integers
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
Input
The input is given from standard input in the following format.
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the minimum number of operations required.
Sample
Sample 1
Input
3 2 2 2
Output
2
For example, by doing $(2, 2, 2) \rightarrow (1, 2, 2) \rightarrow (1, 2, 3)$, the goal can be achieved with $2$ operations.
Sample 2
Input
4 1 2 2 3
Output
2
For example, by doing $(1, 2, 2, 3) \rightarrow (1, 1, 2, 3) \rightarrow (0, 1, 2, 3)$, the goal can be achieved with $2$ operations.
Elements of $A$ may become $0$ or negative as a result of the operations.
Sample 3
Input
4 1 1 1 1
Output
4
Sample 4
Input
9 9 9 8 2 4 4 3 5 3
Output
5
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。