一道acm题目

2025-03-25 21:01:54

推荐回答（3个）

回答1：

直接深搜就可以了吧，开一个数组记录，把所有相等的巧克力重量设为1
遇到3<4这种就分支成两种情况，把3的重量设为0继续深搜出现矛盾就返回，再把4的重量设为2，深搜出现矛盾就返回，如果所有分支都出现矛盾，那么就是无法判断，如果有一条分支符合所有条件，那么那条分支的假设就是对的，比如之前把3设为0那么该条路线的假设就是3是坏的，如果把4设为2那么假设就是4是坏的

回答2：

对于等号左右的巧克力编号不用考虑，这些编号的巧克力肯定是好的。对于不等号左右的巧克力，假设这些巧克力巧克力总共有m个，枚举这m个巧克力，假设某一个为质量大或者质量小的，而后带入题目看是否成立，若成立便找到了坏的巧克力。复杂度是O(2^m)，在m较小时可行。

回答3：

题目来源是哪个OJ？直接给地址啊。