国家集训队作业程序sgu.pdfVIP

SGU306 Balance 解题 浙江省杭州二中 骞 题目大意： n 个球中有一个是坏的，重量和其它不一样，其它的重量都是一样的。现在有一个天平， 请给出一种称球的方案，使得 情况下，称出坏球的次数最小。 方法： 因为天平每一次会返回三种结果——相等、左边重、右边重，而一共的状态有2*n 种（n 个球，轻重两种情况），所以要称出哪个球轻了或者重了的次数下限是 有了标准球之后 1、当前的球没有被称过。 那么好象 回到了初始时的状态，但其实 这时已经拥有了标准球，可以应付有 3k+1 个球的情况。那就是用k+1 个球和k 个球加一个标准球去称，这样，如果平衡，状态 只剩下了2k；如果一边轻或者重，状态也只剩下了2k+1 。这样就满足了3 分的条件。还有 一个问题，那就是现在有m+1 个球，本来应该有2m+2 种状态，但 希望这里只有2m+1 种状态。其实， 假设其中的第 m+1 个球，只有一种状态，要么好的，要么坏的，这样 总的状态数就只有2m+1 了。这样所对应的策略就是永远都不将第m+1 个球放上天平，那 么如果最后只剩余了这个球，本来有两种状态——轻或者重，但是这里 直接输出这个球 是坏的，而不管它是轻是重。 2 、有m+n 个已经在天平上称过的球，其中的m 个要么是好的，要么是轻的；另外的n 个要么是好的，要么是重的。此时又要分几种小情况来 。 1） m=3p ，n=3q 时，那么 从可能轻的3p 中选出p 个放在A 组中，选p 个 放在B 组中，再从可能重的3q 中选出q 个放在A 组中，选q 个放在B 组 中。然后 称A 和B ，如果A 比B 重，那么显然要么是轻的放在B 中的 p 个有问题，要么是重的放在A 中的q 个有问题，这样的剩余状态是p+q ， 满足条件。同理，A 比B 轻也满足条件。如果A 和B 一样中，那就是A 中 没有称的p 个或者B 中没有称的q 个有问题，同样满足条件。 2 ） m=3p+1, n=3q+1 。此时， 希望称一次后剩余状态不超过p+q+1 。这里 就要借助标准球。将m 中的p+1 和p 个分别放在A 和B 组中，把n 中的q 和q 个分别放在A 和B 组中，由于A 和B 组中球个数不一样，所以 须在B 中补一个标准球。此时， 就能满足条件了。 那么同理，m 模3 有3 种情况，n 模3 有3 种情况，它们的组合一共有9 种情况。 其他的几种就不在这里详细说明，具体可以参考程序或者自己思考。 程序 #include <stdio.h> #include <memory.h> #include <stdlib.h> n, standard; void pr Set( *A) { pr f("%d", A[1]); for( i=2; i<=A[0]; i++) pr f("+%d", A[i]); } void check( *a) { if (a[a[0]] == standard) a[0]--; } void make2( *A, *B, d); void make3( *A, d) { if (A[0] == 1) { for( i=0; i<d; i++) pr f(" "); pr f("fake %d\n", A[1]); return; } *a = new [A[0]/3+2], *b = new [A[0]/3+2], *c = new [A[0]/3+2]; a[0] = b[0] = c[0] = 0; for( i=1; i<=A[0]/3; i++)