There is a group of n people Some of them might be liars who always tell lies Other people always tell the truth The i-th person says There are at least li liars amongst us Determine if what people ar

题意简述

有 $n$ 个人，其中一些人说谎，另一些人说真话，第 $i$ 个人说：“在我们中至少有 $l_i$ 个人是说谎的”。要求根据所有人的话，判断是否存在矛盾，如果没有则输出说谎者的个数。

思路分析

首先考虑一种特殊情况，即所有人都说谎或者都说实话。这时，如果说谎者的个数 $S$ 不等于任何一个人说的 $l_i$，就必然存在矛盾。

否则，我们可以尝试构造一组解。对于每个人，如果他说谎，就假设他是说谎者，否则就假设他是诚实人。这么做的正确性如下：

• 如果假设矛盾，即假设 $S$ 个人说谎，但是有人说至少有 $S+1$ 个人说谎，那么我们假设这个人是诚实的，就会得到与原先假设相矛盾的答案，因此假设不矛盾。
• 如果有人说的数量和假设的 $S$ 的数量不一样，那么说明假设是矛盾的，因为这个人的话既不能被真实情况所满足，又不能被假设满足。
• 对于说谎者，假设他是说谎者，那么他的说法就是假的，与假设的 $S$ 相矛盾；而对于诚实人，假设他是诚实人，那么他的说法就是真的，与假设的 $S$ 相符。

如果没有矛盾，那么假设的 $S$ 就是一个合法的解。由于可能存在多个合法解，我们可以随意输出其中之一。

代码实现

按照思路实现即可。注意，题目中说所有人都可能说谎，因此 $l_i=0$ 也是可能的。此外，注意多组数据