我在解决这个问题：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.
现在我无法证明为什么这种贪婪的方法在数学上是正确的。
最佳答案
这实际上是一个缓存问题-地板是缓存，而self是主内存。
你给出的算法是最优的，因为它只是clairvoyant algorithm。这是一个经典的算法，你可以在很多操作系统资源中找到它。
网上也有一些，例如here和here。
关于algorithm - 贪婪方法证明http://www.spoj.com/problems/SAM/，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16986228/