我正在解决这个问题：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.
现在我无法证明为什么这种贪婪类型的方法在数学上是正确的。