本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总
【题目来源】
AcWing：280. 陪审团 - AcWing题库
【题目描述】
在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。
陪审团是由法官从公民中挑选的。
法官先随机挑选N NN个人（编号1 , 2 … , N 1,2…,N1,2…,N）作为陪审团的候选人，然后再从这N NN个人中按照下列方法选出M MM人组成陪审团。
首先，参与诉讼的控方和辩方会给所有候选人打分，分值在0 00到20 2020之间。
第i ii个人的得分分别记为p [ i ] p[i]p[i]和d [ i ] d[i]d[i]。
为了公平起见，法官选出的M MM个人必须满足：辩方总分D DD和控方总分P PP的差的绝对值∣ D − P ∣ |D−P|∣D−P∣最小。
如果选择方法不唯一，那么再从中选择辨控双方总分之和D + P D+PD+P最大的方案。
求最终的陪审团获得的辩方总分D DD、控方总分P PP，以及陪审团人选的编号。
注意：若陪审团的人选方案不唯一，则任意输出一组合法方案即可。
【输入】
输入包含多组测试数据。
每组测试数据第一行包含两个整数N NN和M MM。
接下来N NN行，每行包含两个整数p [ i ] p[i]p[i]和d [ i ] d[i]d[i]。
每组测试数据之间隔一个空行。
当输入数据N = 0 N=0N=0，M = 0 M=0M=0时，表示结束输入，该数据无需处理。
【输出】
对于每组数据，第一行输出Jury #C，C CC为数据编号，从1 11开始。
第二行输出Best jury has value P for prosecution and value D for defence:，P PP为控方总分，D DD为辩方总分。
第三行输出按升序排列的陪审人选编号，每个编号前输出一个空格。
每组数据输出完后，输出一个空行。
【输入样例】
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【算法标签】
#01背包
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=205,M=805,base=400;// N: 最大候选人数量，M: 总分差范围，base: 偏移量intn,m,p[N],d[N];// n: 候选人数量，m: 需要选择的候选人数量，p[N]: 起诉分数，d[N]: 辩护分数intf[N][25][M],ans[N];// f[i][j][k]: 前i个人中选择j个人，总分差为k时的最大总分和，ans[N]: 选择的候选人编号intmain(){intt=1;// 测试用例编号while(cin>>n>>m,n||m)// 读取n和m，直到都为0结束{for(inti=1;i<=n;i++)// 读取每个候选人的分数cin>>p[i]>>d[i];memset(f,-0x3f,sizeof(f));// 初始化f为负无穷f[0][0][base]=0;// 基础状态：不选人，人数为0，分数差为0（base表示偏移后的0）for(inti=1;i<=n;i++)// 遍历所有候选人for(intj=0;j<=m;j++)// 遍历选择的人数for(intk=0;k<M;k++)// 遍历可能的分数差{f[i][j][k]=f[i-1][j][k];// 不选第i个人intt=k-(p[i]-d[i]);// 选第i个人时的分数差偏移if(t<0||j<1)// 如果越界或人数不足continue;f[i][j][k]=max(f[i][j][k],f[i-1][j-1][t]+p[i]+d[i]);// 选第i个人}intv=0;// 分数差绝对值// 找到最接近0的有效分数差while(f[n][m][base+v]<0&&f[n][m][base-v]<0){v++;}if(f[n][m][base+v]>f[n][m][base-v])// 正方向分数差的总分更大v=base+v;else// 负方向分数差的总分更大v=base-v;// 回溯构造选择的候选人列表inti=n,j=m,k=v;intcnt=0;// 选择的候选人数量while(j)// 当还需要选择候选人时{if(f[i][j][k]==f[i-1][j][k])// 第i个人未被选择{i--;}else// 第i个人被选择{ans[cnt++]=i;// 记录选择的候选人编号k=k-(p[i]-d[i]);// 更新分数差i--,j--;// 移动到前一个候选人和减少选择人数}}inta=0,b=0;// 起诉总分和辩护总分for(inti=0;i<cnt;i++)// 计算总分a+=p[ans[i]],b+=d[ans[i]];printf("Jury #%d\n",t);printf("Best jury has value %d for prosecution and value %d for defence:\n",a,b);sort(ans,ans+cnt);// 排序输出编号for(inti=0;i<cnt;i++)cout<<" "<<ans[i];cout<<endl;cout<<endl;t++;}return0;}【运行结果】
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
