1

コードフォースの練習問題の達成から問題を解決していました。効率的な解決策を見つけることができません。次の問題を解決するにはどうすればよいですか? 強引な解決策しか思い浮かばない

Polycarpus には、n 個の整数 a1、a2、...、an からなる配列があります。Polycarpus は、配列内の数値が一致することを好みます。そのため、彼は配列にできるだけ多くの等しい数を持たせたいと考えています。そのために、Polycarpus は次の操作を複数回実行します。

配列 ai, aj (i ≠ j) の 2 つの要素を選択します。彼は同時に、数値 ai を 1 増やし、数値 aj を 1 減らします。つまり、ai = ai + 1 と aj = aj - 1 を実行します。指定された操作は、正確に 2 つの異なる配列要素を変更します。Polycarpus は、記述された操作を無限に適用できます。

ここで、彼は、そのような操作を任意の回数実行した場合に取得できる等しい配列要素の最大数を知りたいと考えています。ポリカルポスを助けて。

入力 最初の行には、整数 n (1 ≤ n ≤ 105) — 配列サイズが含まれます。2 行目には、スペースで区切られた整数 a1、a2、...、an (|ai| ≤ 104) — 元の配列が含まれます。

出力 単一の整数を出力します。指定された操作を任意の回数実行した場合に取得できる等しい配列要素の最大数です。

Sample test(s)
input
2
2 1
output
1
input
3
1 4 1
output
3
4

1 に答える 1

5

すべての要素の合計を見つける.

sum%n==0 の場合 n でなければ n-1

編集：説明：

まず第一に、答えが最小 n-1 であることを見つけるのは非常に簡単です。

証明: ターゲットとして作成したい任意の数を選択します。最後のインデックス n を想定します。次に、a1 と an に演算を適用して a1=ターゲットを作成します。同様に a2 と an などにも同様に適用します。したがって、最後のインデックスを除くすべての数値1つはターゲットに等しい。

ここで、sum%n==0 の場合、すべての数値が可能であることを確認する必要があります。ここで、すべての数値の平均としてターゲットを選択できることは明らかです。値を平均よりも大きくし、そのうちの 1 つ (場合によっては両方) を平均に等しくします。

于 2012-11-21T16:27:16.960 に答える