本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing280. 陪审团 - 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 DPDP最大的方案。求最终的陪审团获得的辩方总分D DD、控方总分P PP以及陪审团人选的编号。注意若陪审团的人选方案不唯一则任意输出一组合法方案即可。【输入】输入包含多组测试数据。每组测试数据第一行包含两个整数N NN和M MM。接下来N NN行每行包含两个整数p [ i ] p[i]p[i]和d [ i ] d[i]d[i]。每组测试数据之间隔一个空行。当输入数据N 0 N0N0M 0 M0M0时表示结束输入该数据无需处理。【输出】对于每组数据第一行输出Jury #CC 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背包【代码详解】#includebits/stdc.husingnamespacestd;constintN205,M805,base400;// 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(){intt1;// 测试用例编号while(cinnm,n||m)// 读取n和m直到都为0结束{for(inti1;in;i)// 读取每个候选人的分数cinp[i]d[i];memset(f,-0x3f,sizeof(f));// 初始化f为负无穷f[0][0][base]0;// 基础状态不选人人数为0分数差为0base表示偏移后的0for(inti1;in;i)// 遍历所有候选人for(intj0;jm;j)// 遍历选择的人数for(intk0;kM;k)// 遍历可能的分数差{f[i][j][k]f[i-1][j][k];// 不选第i个人inttk-(p[i]-d[i]);// 选第i个人时的分数差偏移if(t0||j1)// 如果越界或人数不足continue;f[i][j][k]max(f[i][j][k],f[i-1][j-1][t]p[i]d[i]);// 选第i个人}intv0;// 分数差绝对值// 找到最接近0的有效分数差while(f[n][m][basev]0f[n][m][base-v]0){v;}if(f[n][m][basev]f[n][m][base-v])// 正方向分数差的总分更大vbasev;else// 负方向分数差的总分更大vbase-v;// 回溯构造选择的候选人列表intin,jm,kv;intcnt0;// 选择的候选人数量while(j)// 当还需要选择候选人时{if(f[i][j][k]f[i-1][j][k])// 第i个人未被选择{i--;}else// 第i个人被选择{ans[cnt]i;// 记录选择的候选人编号kk-(p[i]-d[i]);// 更新分数差i--,j--;// 移动到前一个候选人和减少选择人数}}inta0,b0;// 起诉总分和辩护总分for(inti0;icnt;i)// 计算总分ap[ans[i]],bd[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,anscnt);// 排序输出编号for(inti0;icnt;i)cout ans[i];coutendl;coutendl;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
