--- title: "陪审团" created: 2025-11-28 tags: - 算法 --- # 陪审团 ## 题目 [陪审团](https://www.acwing.com/problem/content/description/282/) ![[image-71c9e7f8.png]] ## 思路分析 首先要找差的绝对值最小 然后再在相同的里面找总和更大的那个 差是分布在-400~400之间的 那么优先是选以0为中心 往左往右拓展的那些 而每一个差 都可能有多种选择方式实现（比如对于差-3 绝对值为3 可能选了1 3这两个人 也可能选了2 5这两个人 只要他们的差的绝对值为3即可） 那么这个问题就转变成了背包问题 在前i个人里选j个人 要求差值为k的所有方案 属性是 要和最大的那一个 即max ![[image-df6eeade.png]] 当然这里比较特殊 有两个不合法的方案 尤其是 在右边集合中 （选i) （1）当j等于0时 j-1为负数 程序上越界了 实际含义为：从前i个人里选0个人 并且包含第i个人的所有方案 显然也是矛盾的 （2）差值只可能在正负400之间 如果k-(p-d)不在这个范围内了就一定是不合法的 不用管它了 之后就是求背包方案的问题了 **思路** 用f[i][j][k]表示从前i个人中选j个人且总差为k的所有方案中的总分最大的方案的总分。（好好理一理） 我们维护这个数组，再找出最小的差值v，那么最大分数的方案即为f[n][m][v]所对应的方案。 /！由于分数0——20，那么一个人的差值（p-d）范围在-20——20,20个人总差值就为-400——400。 定一个偏移量base=400，全部加上base即可使总差值变为0——800。！/ **代码段落：** 输入——维护f数组——找最小差值v——找入选的人——计算人选的两个总分——输出 **分段讲解：** **A：维护f数组。** 对于第i个人，只有选与不选的两种情况。 一、不选，则f[i][j][k]=f[i-1][j][k]。 二、选，那么i需要减少，j（还未入选人数）也要减少，且k（总差值）应减去第i人的差值（p[i]-d[i]）。 由于f表示总分,所以还需要加上第i人的总分（d[i]+p[i]）。 综上，f[i][j][k]=f[i-1][j-1][k-(p[i]-d[i])]+d[i]+p[i]; 注意，应该先判断是否能加入第i人，也就是说要先判断j减去1后会不会小于0， 以及k减去第i人的差值后会不会越界（也就是小于0，或大于最大值800）。 最后从选与不选中选择可行且值最大的方案。 **B:找最小差值v。** 我们先将v设为0(也就是最理想的情况)。 然后判断，方法是看f[n][m][v+base]和f[n][m][base-v]是否都小于0， 若都小于0，则说明不存在此种情况，则v++，利用while循环找出最小的v值。 此外可能出现base+v和base-v都合法的情况，则需要判断哪一个的总分最大（就是将f值比大小） 将v赋成那个方案所对应的v值（注意加上base） **C：找入选的人。** 反过来推。首先从f[i][j][v]开始，(i=n,j=m,这里的v是上面找出来的最小差值加上base)开始， 判断他是由哪一种情况得来（选与不选），若是不选，直接将i--；若选，记录人选，将v减掉该人的差值， 再i--，j--。 相当的复杂…… ## 代码实现 ```cpp #include using namespace std; const int N=210,M=810,base=400;//往右偏移400 使最小值变成0 int p[N],d[N]; int dp[N][21][M]; int n,m; int ans[N]; int main() { int T=1; while(cin>>n>>m && (n || m)) { for(int i=1;i<=n;i++) cin>>p[i]>>d[i]; memset(dp,-0x3f,sizeof dp);//有多轮数据 进行重置 dp[0][0][base]=0;//从0个人里选0个人 差值是0 也就是base（偏移一下） for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;k=M) continue; //剩下的就都是合法方案了 dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][t]+d[i]+p[i]); } } } //由此一来 所有的状态就都初始化出来了 //现在只要找差的最小的是多少 int v=0; //若差值为正负v的时候不存在方案 就扩大差值的范围 //这一过程可以理解成 从0开始找 靠近0的是最优的嘛 但是不一定存在这个解 //如果不存在就往两边延升 去找合法的最小的解 //因为一开始就把-400偏移到了0 所以这里可以直接在400处+-v进行这个找最优解的操作 while(dp[n][m][base-v]<0 && dp[n][m][base+v]<0) v++; //循环结束自然就找到了那个最小的差值 现在就要找负的和正的两个里面 哪个的和更大 if(dp[n][m][base-v]>dp[n][m][base+v]) v=base-v; else v=base+v; //记录方案 int cnt=0; int i=n,j=m,k=v; //再往回做一次状态转移 while(j)//因为要选出m个人 所以没选完就一直做 { //判断能否不选第i个方案 if(dp[i][j][k]==dp[i-1][j][k]) i--; else//一定要选i的话 { ans[cnt++]=i;//把这个方案记下来 //更新状态 k-=(p[i]-d[i]); i--,j--; } } //要求输出 d的总和 p的总和 以及所有选出来的人 int sp=0,sd=0; //枚举所有选出来的人 把d，p的和求出来 for(int i=0;i