問題一覧 > 通常問題

No.1285 Garbage Disposal

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 304
作問者 : piddy / テスター : kya_ski
お気に入りにしたユーザー ProblemId : 5376 / 自分の提出
問題文最終更新日: 2020-10-15 20:26:24
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. Back to the original
yukicoder contest 274 (順位表) の他の問題:

Problem Statement

Piddy's room contains empty instant noodle cups of $N$ kinds, $1$ of each, and the container size of the $i$-th empty cup is $A_i$. Piddy is going to throw away these $N$ items, but since throwing them away separately is space-inefficient, he wants to stack the containers as much as possible when throwing them away.
For distinct integers $i,\ j$, containers $i,\ j$ can be stacked and thrown away if and only if $A_i + 1 < A_j$ holds. (It is also possible to stack $3$ or more containers.)
What is the minimum possible number of groups of containers to throw away?

Input

$N$
$A_1$
$A_2$
$\dots$
$A_N$

  • $1 \le N \le 10^5$
  • $1 \le A_i \le 10^9\ (1 \le i \le N)$
  • $A_i \neq A_j\ (1 \le i < j \le N)$
  • All inputs are given as integers.

Output

Output the answer on $1$ line, followed by a newline.

Sample

Sample 1
Input
3
14
15
9
Output
2

Container $1$ and container $2$ cannot be stacked, but container $3$ can be stacked with either container $1$ or container $2$, only one of them. Therefore, the answer is $2$.

Sample 2
Input
2
7
18
Output
1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。