|
#2
郁闷的终结2014-02-01 11:52
|
有n个罐子，有k个硬币，每个罐子可以容纳任意数量的硬币。罐子是不透明的，起初你可以随机把这k个硬币任意放在罐子里。然后罐子被打乱顺序，你从外表无 法区别罐子。最后罐子被编上号1-n。你有p次机会，每次你可以选择某个罐子，如果该罐子里有硬币，则你可以得到1个（你不可以知道该罐子里有多少硬 币），如果该罐子是空的，你得不到任何硬币。你最终要得到至少c枚硬币，我们的问题是给定n,k,c，求出最少的p，存在一种你最初放硬币的方式，无论罐 子如何被打乱顺序，你都能p次机会内获得至少c个硬币。
输入n,k,c (0 < n <=1000000, 0 < c <= k <=1000000)。
输出，最小的p值。
例如n = 3, k = 6, c = 4。 你可以把每个罐子放入两个硬币，这样得到4次机会可以得到4个硬币，输出4。
我想无论如何打乱顺序，对于每一个罐子来说，只用两种情况，有或者没有，可以有动态数组来存储，最少的一种是p=c,每一个罐子里面都有一个，刚好拿到c个就好。可是好像不对，求助