2

私はこの問題を解決していました: http://www.spoj.com/status/SAM,iiit/
どういうわけか解決策にたどり着きましたが、まだ数学的に証明できません。

問題文とは:

There are 'n' toys (1<=n<=10^5) on a shelf.A child is on the floor.He demands toys in
a sequence to play with , specified by 'p' (1<=p<=5*10^5).His mother gives him a toy
from the shelf if the child demanded a toy which is not on floor.At a time only
'k'(1<=k<=n) toys can be there on floor.So mother when giving toy from shelf can pick a
toy from floor and put it back to shelf if she wants.
So we have to minimize total number of times mother picks toys from shelf.

私の解決策:
(a)変数と関数:

Keep a set of toys on floor and a variable ans(initially 0),which stores the answer.
Also next[],next[i] tells when will toy number 'i' come next in the demand sequence,
ie. index of its next occurrence in demand sequence.
update next[x] updates next[x] to store the next index of its occurrence in  demand 
sequence.If there is no further occurrence next[x]=MAX_INTEGER;

(b) アルゴリズム

Following are the cases:
1.If child demands a 'x' toy from shelf:
  increment ans
  If there are less than k elements then:
       add the element to the set
       update next[x]
  If there are k elements:
      remove the element from set whose value of next[] is largest
      add element 'x' to set 
      update next[x]
2.If child demands toy from floor say toy 'x':
  update next[x]
ans is the final answer.

この貪欲な型のアプローチが数学的に正しい理由を証明することはできません。

4

1 に答える 1

2

これは実際にはキャッシングの問題です。フロアはキャッシュであり、セルフはメイン メモリです。

あなたが与えたアルゴリズムは、千里眼のアルゴリズムであるため、最適です。これは古典的なアルゴリズムであり、多くのオペレーティング システム リソースで見つけることができます。

ここやここなど、オンラインにもいくつかあります。

于 2013-06-07T14:16:37.850 に答える