题目描述
在一个遥远的国家,一名嫌疑犯是否有罪需要由陪审团来决定。
陪审团是由法官从公民中挑选的。
法官先随机挑选N个人(编号1,2…,N)作为陪审团的候选人,然后再从这N个人中按照下列方法选出M人组成陪审团。
首先,参与诉讼的控方和辩方会给所有候选人打分,分值在0到20之间。
第 i 个人的得分分别记为p[i]和d[i]。
为了公平起见,法官选出的M个人必须满足:辩方总分D和控方总分P的差的绝对值|D-P|最小。
如果选择方法不唯一,那么再从中选择辨控双方总分之和D+P最大的方案。
求最终的陪审团获得的辩方总分D、控方总分P,以及陪审团人选的编号。
输入格式
输入包含多组测试数据。
每组测试数据第一行包含两个整数N和M。
接下来N行,每行包含两个整数p[i]和d[i]。
每组测试数据之间隔一个空行。
当输入数据N=0,M=0时,表示结束输入,该数据无需处理。
输出格式
对于每组数据,第一行输出’Jury #C’,C为数据编号,从1开始。
第二行输出“Best jury has value P for prosecution and value D for defence:”,P为控方总分,D为辩方总分。
第三行输出按升序排列的陪审人选编号,每个编号前输出一个空格。
每组数据输出完后,输出一个空行。
数据范围
1≤N≤200,
1≤M≤20
样例
输入样例:
4 2
1 2
2 3
4 1
6 2
0 0
输出样例:
Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3
算法1
(暴力枚举) $O(n^2)$
这是一道具有多个”体积维度”的0/1背包问题.把N个候选人看作N个物品,
那么每个物品有如下三种”体积”:
1.”人数”,每个”候选人”的”人数”都是1,最终要填满容量为M的背包.
2.”辨方的分”,即辨方给该候选人打的分数a[i],一个0到20的整数.
3.”控方的分”,即控方给该候选人打的分数b[i],一个0到20的整数.
因此,我们依次考虑每个候选人是否选入评审区,当外层循环到阶段i时,表示已经考虑了前i个候选人的入选情况,此时用Boolean数组F[j,d,p]表示已有j人被选入评审团,当前辨方总分为d、控方总分为p的状态是否可行.
F[j,d,p]=F[j,d,p] or F[j-1,d-a[i],p-b[i]]
初值:f[0,0,0]=turn,其余均为false.
目标:找到一个状态F[M,d,p],满足F[M,d,p]=true,而且|d-p|尽量小,|d-p|相同时d+p尽量大.
上述算法没有很好的利用背包”价值”这一维度,还有很大的优化空间.实际上,我们可以把每个候选人辨、控双方得分的差a[i]-b[i]作为该物品的”体积”之一,把辨、控双方得分的和作为该物品的价值.
当外层循环到i时,设F[j,k]表示已经在前i个候选人中选出了个j个,此时辨方总分与控方总分的差为k时,辨方总分与控方总分的和的最大值.
F[j,k]=max(F[j,k],F[j-1,k-(a[i]-b[i])]+a[i]+b[i])
初值:F[0,0]=0,其余均为负无穷大.
目标:找到一个状态F[M,k],满足|k|尽量小,当|k|相同时F[M,k]尽量大.
在转移中,注意对j这一维度执行倒序循环,即可保证每个候选人只会被选一次,符合0/1背包的特征.
本题还要求输出评审团入选的具体方案.我们采用记录转移路径的方法,即额外建立一个数组D,其中D[j,k]记录状态F[j,k]的最大值是选了哪一名候选人而得到的.
在求出得优解后,我们沿着数组D记录的转移路径,不断从状态F[j,k]递归到F[j-1,k-(a[D[j,k]]-b[D[j,k]])],直至到达F[0,0].递归过程中的所有D[j,k]就构成了评审团的入选.
时间复杂度分析:blablabla
C++ 代码
暂时没有
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
C++ 代码
blablabla
既然暂时没有,就贴一个上去/doge
不给CODE的题解都是耍流氓-yan总