ABC473 C - Change Schools
転校
考え方
ややこしいことを言っているように見えるが、丁寧に読めば実は非常に単純なことを言っている。
以下のいずれかに該当するクラスはいくつあるか、ということである。
- 現時点でクラスの人数が最大である。
- 現時点でクラスの人数が最大より $1$ 小さいだけで、高橋君が加われば最大タイになる。
ということで、各クラスに何人いるかカウンティングすることを思いつけば、あとは簡単。
全体を一度見て最大値を求めた後に、もう一度全体を見て条件を満たす個数を数えればよい。
計算量は $O(N+K)$ である。
入力例1での動作
入力を受け取る。
n: 8
k: 5
a: {3, 3, 5, 5, 4, 4, 3, 2}各クラスの人数を数えると、次のようになる。
| クラス | 人数 |
|---|---|
| $1$ | $0$ |
| $2$ | $1$ |
| $3$ | $3$ |
| $4$ | $2$ |
| $5$ | $2$ |
最大人数は $3$ 人である。
したがって、現在の人数が $3$ 人、またはそれより $1$ 少ない $2$ 人であるクラスを数える。
条件を満たすのはクラス $3,4,5$ の $3$ クラスなので、答えは $3$ となる。
注意点
特になし。
別解
特になし。