回复：[一些小小的想法]记我在KFC看到的光芒，度过的日子
以下引用wdx04在2005-11-13 9:06:28的发言：
信息学竞赛...那么我给个题目吧，算法比较简单，理解了题意就能做出来。
邮箱制造商的问题
从前，当瑞典的小孩仍被允许玩爆竹的时候，成群结队的兴奋的孩子们常常给他们居住的城市带来麻烦，他们喜欢用爆竹把东西炸毁。较小的箱子容易被炸毁，所以邮箱成了一个热门的攻击目标。现在，一个邮箱制造商想知道他们生产的新邮箱能够承受多少爆竹的同时爆炸而不被炸毁。因此他雇佣你来帮助他。他会给你k(1<=k<=10)个完全相同的邮箱，每个邮箱最多能放进m(1<=m<=100)个爆竹(所有爆竹也都相同)。但是，他不知道需要给你多少个爆竹，才够解决这个问题，因此求教于你。你想了一会儿说：“是啊，一个邮箱被炸毁之后，就不能够再用了，所以，如果你只给我k=1个邮箱，我就不得不从1个爆竹，2个爆竹开始测试，直到邮箱被炸毁。在最坏的情况下，邮箱直到被塞满也不会被炸毁，那就需要1+2+3+...+m=m*(m+1)/2个爆竹。如果m=100，这意味着需要5000个以上的爆竹！”“那也太多了。”他回答道：“如果我给你k=1个以上的邮箱呢？你能找到一种需要较少的爆竹的策略吗？”
你能吗？你需要向他要求提供的最少的爆竹数是多少？
你可以假设如下事实成立：
1、如果一个邮箱可以承受x个爆竹的同时爆炸，那么它一定能承受x-1个爆竹的同时爆炸。
2、经过一次爆炸，一个邮箱要么就是被炸毁，要么就是完好无损，可以像新的邮箱一样继续用于测试。
注：如果邮箱在装满爆竹时仍不会被炸毁，制造商将很满足于这个结果。但如果不是那样，他希望找出邮箱的最大承受能力。
输入规约：
每个输入文件第一行是单个整数N(1<=N<=10)，表示测试用例的个数。后面每个测试用例占一行，包含两个整数，k和m，中间用单个空格符分隔。
输出规约：
每个测试用例的结果占一行，包含单个整数，表示在最坏的情况下，为了找出邮箱的最大承受能力，需要的爆竹数。
范例输入：
4
1 10
1 100
3 73
5 100
范例输出：
55
5050
382
495
|
以下的算法仅供参考（因为不一定是最优的）：
如果只有一个邮箱，最坏的情况就是1+2+3+...+m=m*(m+1)/2个，但是，如果邮箱不止一个，多出来的邮箱就可以作为“二分法”查找的材料。即：
先把m/2个爆竹放进一个邮箱中，如果他没炸，则用m/2+m/4个爆竹测试，如果它炸了，就用m/4个爆竹测试第二个邮箱，直到测出准确值或只剩下一个邮箱为止。这样，每测试一次，测试范围就会缩小一半。如果只剩一个邮箱时仍没有测出准确值，就只能在确定出的测试范围中从小到大测试了（因为邮箱只剩一个了，我们输不起了）。
这个方法的最坏情况
并不是“二分法查找的阶段中，每次邮箱都被炸坏，最后的逐一测试时直到测试到最大值邮箱才炸。”
只有对邮箱的承受能力进行穷举测试，才能找出最坏的情况，也就是说，假设承受能力是1至m，依次应用上述算法求最大爆竹消耗量并取其中最大的，那才是最坏的情况。
我觉得在这里使用“二分法”的思想该可以，但是分界点并不一定是1/2，测试多个分界点可能能找出真正的最优算法，但是那必须对上述算法再加上一层穷举过程，并从所有分界点对应的最坏情况中找出消耗最少的来作为最优分界点。
KCDDP KR/KAG区值班室常驻义务值班员
现在在KCDDP的论坛也已经开始潜水了Orz
但是QQ群还是长期在线的
