ACM一道算法题,我的算法为何WADescription There is N pairs of balls in a small box.That means the number for each pair is the same.However,for some reason,a ball is lost.Now,you will get the number of the rest.Can you find the number of the
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/08 11:44:57
ACM一道算法题,我的算法为何WADescription There is N pairs of balls in a small box.That means the number for each pair is the same.However,for some reason,a ball is lost.Now,you will get the number of the rest.Can you find the number of the
ACM一道算法题,我的算法为何WA
Description
There is N pairs of balls in a small box.That means the number for each pair is the same.However,for some reason,a ball is lost.Now,you will get the number of the rest.Can you find the number of the lost ball as fast as possible?
Input
The input consists of several test cases.For each case,the first line contains an integer N(1
ACM一道算法题,我的算法为何WADescription There is N pairs of balls in a small box.That means the number for each pair is the same.However,for some reason,a ball is lost.Now,you will get the number of the rest.Can you find the number of the
楼主的算法应该是没有问题的,问题可能出在具体的实现上,因为没有代码,也不好推断问题所在.
刚才实现了楼主的算法,结果也是WA.
遂又尝试了一下二叉排序树法,依然WA……
然后呢,我把两种方法都进行了下改进,设置了检查条件,如果有超过一个不成对的数字出现,就进入死循环,结果是,两种算法都会超时.
所以,说一下我的猜测（对,是猜测,因为我不能完全保证我的算法实现了我的想法,也就不能证明我的推测是正确的）,那就是,测试数据并不像题目描述那样,除一个数字之外,其余全部两两成对.
异或的算法确实能保证在数据如题目描述的情况下求得正确答案,但它在数据错误时也能得出一个解,并且无法检查数据的正确性.
所以,我再进行一个大胆的猜想,这道题目的数据制作者,是假定了这样一种算法为正确解法,然后呢,用了某种不能保证符合题目描述的方法生成了测试数据,再用这种算法得到了参考答案,却没有用其它算法进行验证……
通过观察这道题的统计数据,我猜大概绝大多数的人都是用这种算法通过的.
再次重申,以上猜测未经严格验证.楼主如果有兴趣,也可以自己试一下:)