3

コンテストが終わったので、この質問についてお聞きしたいと思います。私は実際にそれを理解することができないので、過去 3 日間、この質問に本当に苦労してきました。

質問は次のとおりです: Facebook Hacker Cup 2013 の分を見つけてください

この質問の解決策を見つけたサイトは次のとおりです 。

私が理解できないのは、次の部分です。

これらの最初の K 値は何でもかまいませんが、最初の K 要素の後の配列の内容について、いくつかの有用な観察を行うことができます。

  1. ピジョンホールの原理により、すべての要素は 0 から K (包括的) の間になります。
  2. したがって、K + 1 個の連続する要素のすべてのウィンドウには、0 から K までの各値が 1 回だけ含まれます (つまり、0 から K までの整数の順列が含まれます)。
  3. したがって、i > 2K の場合: M[i] = M[i - (K + 1)]。

最初の点が真実であれば、2番目と3番目の点は理解できますが。最初のものは実際に私を悩ませています。要素が 0 から K の間にある必要があるのはなぜですか。最初の K 要素に存在しない最小の負でない整数だけをすべての要素にできないのはなぜですか。

例: 次のテスト ケースの場合:

1

46 18

7 11 9 46

最初の K 要素は次のとおりです。

[7, 40, 35, 26, 19, 34, 15, 36, 37, 2, 31, 28, 41, 0, 9, 16, 1, 20]

以前の K 要素に 18 を超える要素があるのに、残りの要素が 0 から 18 の間でなければならないのはなぜですか。

4

1 に答える 1

3

K 個の数字{a0,a1,a2...a(k-1)}があり、その中にない最初の非負の数字を見つけたいとします。以上のことはできますKか？そうであれば、すべての数字{0,1,...K}が上記のセットに存在し、数字K+1で構成される上記のセットに数字が存在する必要がありKます。これは不可能であり、新しい数が より大きいという仮定と矛盾しKます。したがって、各ステップで追加する次の数字は範囲内[0,K]にあるため、K+1ステップでは最後のすべてのK+1数字がそのステップに含まれるため、その範囲内の異なる数字になります。

于 2013-01-29T14:26:53.843 に答える