1660B Vlad and Candies(機械翻訳直訳のみ)

問題

少し前まで、Vladには誕生日があり、そのためにキャンディーのパッケージが贈られました。キャンディーにはn種類あり、 $タイプi （1 \leq i \leq n）のa_{i}種$ のキャンディーがあります。

Vladは、現在最も頻繁に使用されているタイプのキャンディーのいずれかを選択して、毎回1つのキャンディーを食べることにしました（そのようなタイプが複数ある場合、彼はそれらのいずれかを選択できます）。食べることを最大限に楽しむために、Vladは同じ種類のキャンディーを2つ続けて食べたくありません。

2つの同じキャンディーを続けて食べることなく、すべてのキャンディーを食べることができるかどうかを彼が理解するのを手伝ってください。

解答

全部で3つのケースがあります、2つのタイプのキャンディーでそれらを考えてみましょう：

$a_{1}= a_{2}$ の場合

キャンディーをこの順序で食べます $a_{1},a_{2},a_{1},a_{2}\cdots a_{1},a_{2}$

$a_{1} = a_{2} + 1$ の場合

次にタイプ1のキャンディーを食べ、次にこの順序で食べます[2,1,2,1、…、2,1] （ほぼ上記の場合と同様）

$a_{1} = a_{2} + 2$ の場合

タイプ1のキャンディーを食べますが、タイプ2のキャンディーよりもまだ多く、タイプ1のキャンディーをもう一度食べる必要があります。したがって、答えは「No」です。
ここで、配列aに存在する最大値と次に最大な値でこれらの条件をチェックするだけで十分であることを証明します。 3番目の条件が真の場合、答えは「No」になります。

それ以外の場合は、最大にある2つのタイプのキャンディーを順番に食べて3番目の最大値に等しくなり、その後、これら3つのタイプのキャンディーを順番に食べます。

補足

タイプXという表記は面倒なため赤・青の2色の(包装のある)キャンディーに例えてみる

YESの場合

(1)赤=青=3

赤→青→赤→青→赤→青

もしくは

青→赤…青→赤

(2)赤=青+1→赤=3 青=2

赤→青→赤→青→赤

先に多い方を食べて次を少ない方にするといい

NOの場合

(3)赤=青+2→赤=4 青=2

赤→青→赤→青

と(2)対応で上手くいきそうだが残っているのは赤が二つなので赤→赤にならざるを得ない。

尚、2以上になっても青を使い切った後残ったのは複数の赤になるためNOになる。

最大の数と、二番目に最大な数で2以上になる場合はNOになる。

赤 = 2 , 青= 6, 黄色 = 5 の場合

一番多い青を赤に合わせるまで青→黄を繰り返す

青 → 黄 → 青→ 黄 → 青 → 黄→青 →黄→青

すると、赤 = 2 , 青=2 ,黄 =1になるのでそこで赤を挟む

赤→青→黄→赤→青とすれば良い