题目:选举统计
问题描述
某地要选举m个代表参加上级会议,请所有参加选举的n个人投票,有t个候选人, 每个选民最多可以选择v个。给定多行整数数列,第一行整数给出m、n、t、v等信息,后面每行对应一个选民的选举结果。每个数列中,第一个数据表示该选民选票上的选项数,后 面的多个数据对应于选举对象序号。根据这些信息对候选人进行唱票,并按照票数排序给出 最终当选的m个候选人。
注意,
1. 给出的m个候选人按选举对象序号从小到大给出。
2. 如果出现因为票数相同而出现并列,导致超出m个的情况,给出排名靠前无异议 当选的候选人的信息,并在下面单独一行给出并列人信息,以供下一轮投票。
3. 一个选民的选票中不应出现超出v个选项的情况,也不应出现重复选项,也不应出 现选择无效候选人的情况,如果出现超项、无效选项或重复选项,则将该选民选票整体作废。
输入格式
输入的第一行包含四个整数m n t v,表示选出代表的个数、选民个数、候选人个数和每 个选民限制选项个数,数据之间以空格隔开。
从第二行起的n行包含多个整数vi, a1, a2, …, avi,表示第i个选民的投票信息,vi为他 选项个数,后面跟着的vi项为他选择的多个选举对象序号。相邻的整数之间用一个空格分 隔。
输出格式 输出一行或两行整数,表示选举结果:
如果刚好选出m个代表,则在一行内按选举对象序号从小到大给出这m个代表的序号;
如果因为并列导致超出m个代表,则在一行内按选举对象序号从小到大给出排名在m名以 内,不是排名并列的代表的序号,并在第二行内给出并列候选人序号,以供下一轮投票使用。
样例输入1
1 4 2 1 1 1 0 1 1 1 1
样例输出1
1
样例输入2
3 11 5 3 3 1 2 3 0 2 1 3 3 2 3 5 3 2 3 4 3 6 5 3 4 1 2 3 4 3 2 3 4 3 5 3 2 3 4 3 4 3 3 4 5
样例输出2
2 3
4 5
样例说明
样例1中,4个选民在2个候选人中选择1个代表,每个选民最多选择1项。四张选票 中有一个选项为0,弃权,其他三张选票均选择了1个有效项。唱票结果为1号候选人获得 3票,其他候选人0票,因此结果为1号候选人获得代表资格。
样例2中,11个选民在5个候选人中选择3个代表,每个选民最多选择3项。11张选 票中,如标注高亮的区域所示,有三张废票。其中,有一张选票中出现了6这个无效选项, 作废;有一张选择了4个选项,作废;还有一张选票中出现了重复选项,也作废;还有一张 选票选了0人,属于弃权票,因此有效选票为7张。
对这些选票进行统计,可以知道,1号 候选得到2票,2号候选得到5票,3号候选得到7票,4号候选得到3票,5号候选得到3 票。可见3号、2号为排名第一、第二候选人,4号、5号因票数相同并列第三,需要进行 下一轮投票决出最终代表。
评测用例规模与约定 1 ≤ n ≤ 100,0 ≤ m ≤ 10, 1 ≤ t ≤ 100,0 ≤ v ≤ 10。
问题描述
某地要选举m个代表参加上级会议,请所有参加选举的n个人投票,有t个候选人, 每个选民最多可以选择v个。给定多行整数数列,第一行整数给出m、n、t、v等信息,后面每行对应一个选民的选举结果。每个数列中,第一个数据表示该选民选票上的选项数,后 面的多个数据对应于选举对象序号。根据这些信息对候选人进行唱票,并按照票数排序给出 最终当选的m个候选人。
注意,
1. 给出的m个候选人按选举对象序号从小到大给出。
2. 如果出现因为票数相同而出现并列,导致超出m个的情况,给出排名靠前无异议 当选的候选人的信息,并在下面单独一行给出并列人信息,以供下一轮投票。
3. 一个选民的选票中不应出现超出v个选项的情况,也不应出现重复选项,也不应出 现选择无效候选人的情况,如果出现超项、无效选项或重复选项,则将该选民选票整体作废。
输入格式
输入的第一行包含四个整数m n t v,表示选出代表的个数、选民个数、候选人个数和每 个选民限制选项个数,数据之间以空格隔开。
从第二行起的n行包含多个整数vi, a1, a2, …, avi,表示第i个选民的投票信息,vi为他 选项个数,后面跟着的vi项为他选择的多个选举对象序号。相邻的整数之间用一个空格分 隔。
输出格式 输出一行或两行整数,表示选举结果:
如果刚好选出m个代表,则在一行内按选举对象序号从小到大给出这m个代表的序号;
如果因为并列导致超出m个代表,则在一行内按选举对象序号从小到大给出排名在m名以 内,不是排名并列的代表的序号,并在第二行内给出并列候选人序号,以供下一轮投票使用。
样例输入1
1 4 2 1 1 1 0 1 1 1 1
样例输出1
1
样例输入2
3 11 5 3 3 1 2 3 0 2 1 3 3 2 3 5 3 2 3 4 3 6 5 3 4 1 2 3 4 3 2 3 4 3 5 3 2 3 4 3 4 3 3 4 5
样例输出2
2 3
4 5
样例说明
样例1中,4个选民在2个候选人中选择1个代表,每个选民最多选择1项。四张选票 中有一个选项为0,弃权,其他三张选票均选择了1个有效项。唱票结果为1号候选人获得 3票,其他候选人0票,因此结果为1号候选人获得代表资格。
样例2中,11个选民在5个候选人中选择3个代表,每个选民最多选择3项。11张选 票中,如标注高亮的区域所示,有三张废票。其中,有一张选票中出现了6这个无效选项, 作废;有一张选择了4个选项,作废;还有一张选票中出现了重复选项,也作废;还有一张 选票选了0人,属于弃权票,因此有效选票为7张。
对这些选票进行统计,可以知道,1号 候选得到2票,2号候选得到5票,3号候选得到7票,4号候选得到3票,5号候选得到3 票。可见3号、2号为排名第一、第二候选人,4号、5号因票数相同并列第三,需要进行 下一轮投票决出最终代表。
评测用例规模与约定 1 ≤ n ≤ 100,0 ≤ m ≤ 10, 1 ≤ t ≤ 100,0 ≤ v ≤ 10。