0

2つの整数N<=10^5とK<=Nが与えられます。ここNで、は配列のサイズでありA[]、Kはプロセスで選択できる連続サブシーケンスの長さです。各要素A[i]<=10^9。ここで、最初に配列のすべての要素がマークされていないとします。各ステップで、長さのサブシーケンスを選択します。Kこのサブシーケンスにマークされていない要素がある場合は、シーケンスで最小のマークされていない要素をすべてマークします。では、すべての要素をマークするための最小ステップ数を計算する方法は？

問題をよりよく理解するには、この例を参照してください-

N=5 K=3 A[]=40 30 40 30 40

ステップ1-間隔[1,3]を選択し、A[1]とA[3]をマークします

ステップ2-間隔[0,2]を選択し、A[0]とA[2]をマークします

ステップ3-間隔[2,4]を選択し、A[4]をマークします

したがって、ここでの最小ステップ数は3です。

私のアプローチ（通過するのに十分な速さではありません）-

私は配列の最初の要素から始めて、距離を置いてそれに等しいすべてのマークされていない要素をマークし、 1<=Kずつ増やしていますsteps。

4

3 に答える 3

3

Kまず、 ==の質問にどのように答えるかを検討しますN（つまり、サブシーケンスの長さに効果的な制限はありません）。答えは、最小ステップ数は配列内の個別の値の数であるということです。

次に、これがK減少するにつれてどのように変化するかを検討します。重要なのは、に存在する各値Kの選択セットをカバーするために必要な長さ間隔のコピーの数です。に沿って長さの間隔を歩き、その値に対してまだカバーされていない各位置で停止するという素朴なアルゴリズムは完全に適切です。{i: A[i] == n}nAKAA[i]n

于 2012-07-02T10:37:21.650 に答える
1

最小ステップ数=N/kまたはN/k + 1であり、最大ステップ数=（n + k-1）であることがわかります。ステップの総数を最適化する必要があります。これは、動的ソリューションを参照する過去の選択履歴に依存します。

動的理論のチュートリアルについては、http： //www.quora.com/Dynamic-Programming/How-do-I-get-better-at-DP-Are-there-some-good-resources-or-tutorials-on-itを参照してください。 -like-the-TopCoder-tutorial-on-DP / answer / Michal-Danil％C3％A1k

于 2012-07-02T10:47:06.910 に答える
0

次のようにO（n）で解くことができます。各要素a[i]をトレースします。a [i]が以前にトレースされていなかった場合は、番号とそのインデックスをマップし、カウンターを増やします。番号が以前にトレースされた場合は、その（last index-curr_index）> = Kかどうかを確認し、はいの場合はインデックスを更新してカウントを増やします。印刷回数。マップSTLは有益です。

于 2012-07-07T12:58:42.227 に答える