#LUOGUP9527. [USACO24JAN] Majority Opinion B
[USACO24JAN] Majority Opinion B
题目描述
Farmer John 有一项重要的任务——弄清楚要为他的奶牛们购买什么类型的干草。
Farmer John 的 头奶牛()编号为 到 ,每头奶牛喜欢恰好一种类型的干草 ()。他希望他的所有奶牛都喜欢同一种干草。
为了实现这一目标,Farmer John 可以主持焦点小组访谈。一次焦点小组访谈为让编号从 到 的连续范围内的所有奶牛聚集在一起参加一次访谈。如果有一种干草是小组中超过一半的奶牛喜欢的,则此次焦点小组访谈结束后,所有奶牛最终都会喜欢这种干草。如果不存在这种类型的干草,那么奶牛们不会改变她们喜欢的干草类型。例如,在由 头奶牛组成的焦点小组访谈中,需要有其中 头或更多的奶牛具有相同的干草喜好,才能使其余奶牛改变其喜好以与之一致。
Farmer John 想知道哪些类型的干草有可能变为同时受到所有奶牛的喜爱。他一次只能主持一个焦点小组访谈,但为了使所有奶牛都喜欢同一类型的干草,他可以根据需要任意多次地主持焦点小组访谈。
输入格式
输入的第一行包含一个整数 ,为独立的测试用例的数量()。
每一个测试用例的第一行包含 。
第二行包含 个整数,为奶牛们喜爱的干草类型 。
输入保证所有测试用例的 之和不超过 。
输出格式
输出 行,对于每个测试用例输出一行。
如果可能使所有奶牛同时喜欢同一种干草,则以升序输出所有可能的此类干草的类型,否则输出 。在同一行内输出一列整数时,相邻的数用空格分隔,并确保行末没有多余空格。
5
5
1 2 2 2 3
6
1 2 3 1 2 3
6
1 1 1 2 2 2
3
3 2 3
2
2 1
2
-1
1 2
3
-1
提示
样例解释
在输入样例中,有 5 个测试用例。
在第一个测试用例中,仅可能使所有奶牛喜欢种类 。FJ 可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。
在第二个测试用例中,可以证明没有奶牛会改变她们喜爱的干草种类。
在第三个测试用例中,有可能使所有奶牛喜欢种类 ,可以通过主持三次焦点小组访谈达到这一目的——首先使奶牛 到 进行一次焦点小组访谈,随后使奶牛 到 进行一次焦点小组访谈,随后使奶牛 到 进行一次焦点小组访谈。以类似的逻辑,依次操作奶牛 到 ,随后是奶牛 到 ,随后是奶牛 到 ,我们可以使所有奶牛喜欢种类 。
在第四个测试用例中,有可能使所有奶牛喜欢种类 ,可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。
在第五个测试用例中,可以证明没有奶牛会改变她们喜爱的干草种类。
测试点性质
- 测试点 :。
- 测试点 :。
- 测试点 :对于所有的 ,有 。
- 测试点 :没有额外限制。