310387: CF1826A. Trust Nobody
Description
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 $l_i$ liars amongst us". Determine if what people are saying is contradictory, or if it is possible. If it is possible, output the number of liars in the group. If there are multiple possible answers, output any one of them.
InputThe first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 100$).
The second line of each test case contains $n$ integers $l_i$ ($0 \leq l_i \leq n$) — the number said by the $i$-th person.
It's guaranteed that the sum of all $n$ does not exceed $10^4$.
OutputFor each test case output a single integer. If what people are saying is contradictory, output $-1$. Otherwise, output the number of liars in the group. If there are multiple possible answers, output any one of them.
ExampleInput7 2 1 2 2 2 2 2 0 0 1 1 1 0 5 5 5 3 3 5 6 5 3 6 6 3 5Output
1 -1 0 -1 0 3 4Note
In the first example, the only possible answer is that the second person is a liar, so the answer is $1$ liar.
In the second example, it can be proven that we can't choose the liars so that all the requirements are satisfied.
In the third example, everybody tells the truth, so the answer is $0$ liars.
Input
题意翻译
**题目描述** 有由 $n$ 个人组成的群体，其中的一部分人被称为“说谎者”，总是说谎话，另一部分人总是说真话。对于 $1\leq i \leq n$ ，第 $i$ 个人说：“在我们中间至少有 $l_i$ 个人说谎话。”写一个程序判断人们所说的是矛盾的，还是可能存在的。如果是可能存在的，输出群体中说谎者的数量，如果有多种可能，输出其中任意一种即可。 **输入格式** 第一行一个整数 $t(1 \leq t \leq 1000)$ ，代表测试数据的组数。 对于每一组测试数据： 第一行一个整数 $n(1 \leq n \leq 100)$ ，代表群体中的人数。 第二行共 $n$ 个数，以空格隔开，对于 $1\leq i \leq n$，第 $i$ 个数代表 $l_i$ 。 数据保证 $\displaystyle\sum n \leq 10^4$。 **输出格式** 对于每一组测试数据，输出一个整数。如果人们所说的是矛盾的，输出 $-1$ ,否则，输出群体中说谎者的数量，如果有多种可能，输出其中任意一种即可。Output
这是一个关于判断一群人中哪些是总是说谎的人的问题。这群人中的每个人都会说：“我们当中至少有$l_i$个说谎者”。需要判断这些人的陈述是否矛盾，如果可能，输出这群人中说谎者的数量。如果有多个可能的答案，输出其中任何一个。
输入数据格式：
第一行包含一个整数$t$（$1 \leq t \leq 1000$），表示测试用例的数量。
每个测试用例的第一行包含一个整数$n$（$1 \leq n \leq 100$），表示人群中的总人数。
每个测试用例的第二行包含$n$个整数$l_i$（$0 \leq l_i \leq n$），表示第$i$个人所说的话。
保证所有测试用例中$n$的总和不超过$10^4$。
输出数据格式：
对于每个测试用例，输出一个整数。如果人们的陈述是矛盾的，输出$-1$。否则，输出这群中说谎者的数量。如果有多个可能的答案，输出其中任何一个。
示例：
输入：
```
7
2
1 2
2
2 2
2
0 0
1
1
1
0
5
5 5 3 3 5
6
5 3 6 6 3 5
```
输出：
```
1
-1
0
-1
0
3
4
```
注意：
- 在第一个示例中，唯一可能的答案是第二个人是说谎者，所以答案是1个说谎者。
- 在第二个示例中，可以证明我们无法选择说谎者以使所有要求都得到满足。
- 在第三个示例中，每个人都说实话，所以答案是0个说谎者。题目大意： 这是一个关于判断一群人中哪些是总是说谎的人的问题。这群人中的每个人都会说：“我们当中至少有$l_i$个说谎者”。需要判断这些人的陈述是否矛盾，如果可能，输出这群人中说谎者的数量。如果有多个可能的答案，输出其中任何一个。 输入数据格式： 第一行包含一个整数$t$（$1 \leq t \leq 1000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数$n$（$1 \leq n \leq 100$），表示人群中的总人数。 每个测试用例的第二行包含$n$个整数$l_i$（$0 \leq l_i \leq n$），表示第$i$个人所说的话。 保证所有测试用例中$n$的总和不超过$10^4$。 输出数据格式： 对于每个测试用例，输出一个整数。如果人们的陈述是矛盾的，输出$-1$。否则，输出这群中说谎者的数量。如果有多个可能的答案，输出其中任何一个。 示例： 输入： ``` 7 2 1 2 2 2 2 2 0 0 1 1 1 0 5 5 5 3 3 5 6 5 3 6 6 3 5 ``` 输出： ``` 1 -1 0 -1 0 3 4 ``` 注意： - 在第一个示例中，唯一可能的答案是第二个人是说谎者，所以答案是1个说谎者。 - 在第二个示例中，可以证明我们无法选择说谎者以使所有要求都得到满足。 - 在第三个示例中，每个人都说实话，所以答案是0个说谎者。