本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P10971 Cookies - 洛谷【题目描述】圣诞老人共有M MM个饼干准备全部分给N NN个孩子。每个孩子有一个贪婪度第i ii个孩子的贪婪度为g i g_igi。如果有a i a_iai个孩子拿到的饼干数比第i ii个孩子多那么第i ii个孩子会产生g i × a i g_i\times a_igi×ai的怨气。给定N NN、M MM和序列g gg圣诞老人请你帮他安排一种分配方式使得每个孩子至少分到一块饼干并且所有孩子的怨气总和最小。【输入】第一行包含两个整数N , M N,MN,M。第二行包含N NN个整数表示g 1 , g 2 , … , g n g_1,g_2,\dots,g_ng1,g2,…,gn。【输出】第一行一个整数表示最小怨气总和。第二行N NN个空格隔开的整数表示每个孩子分到的饼干数若有多种方案输出任意一种均可。【输入样例】3 20 1 2 3【输出样例】2 2 9 9【算法标签】#提高plus #线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;typedefpairint,intPII;// 定义键值对类型用于记录路径constintN35,M5005;// 常量定义最大孩子数和最大糖果数intn,m;// n: 孩子数量m: 糖果总数ints[N];// 前缀和数组s[i]表示前i个孩子的不满值之和intf[N][M];// DP数组f[i][j]表示前i个孩子分配j个糖果的最小总怨气值PII pre[N][M];// 路径记录数组记录状态转移的前驱状态intans[N];// 结果数组记录每个孩子分配的糖果数structNode{intg,idx;// g: 孩子的不满值idx: 孩子原始编号}c[N];// 比较函数按不满值从大到小排序boolcmp(Node x,Node y){returnx.gy.g;}// 递归打印路径函数根据记录的前驱状态回溯voidprint_path(PII now){intchildnow.first,cooknow.second;// child: 当前孩子数cook: 当前糖果数if(child0)return;// 递归终止条件没有孩子print_path(pre[child][cook]);// 递归处理前驱状态intpre_childpre[child][cook].first;// 前驱状态的孩子数if(pre_childchild)// 如果前驱状态孩子数相同说明当前组每人分到一个糖果{for(inti1;ichild;i)// 给当前组所有孩子分配糖果ans[c[i].idx];}else// 否则说明当前组是新的一组{for(intipre_child1;ichild;i)// 给新组的所有孩子分配糖果ans[c[i].idx];}}intmain(){cinnm;// 输入孩子数量和糖果总数for(inti1;in;i)// 输入每个孩子的不满值{cinc[i].g;c[i].idxi;// 记录原始编号}sort(c1,cn1,cmp);// 按不满值从大到小排序for(inti1;in;i)// 计算前缀和s[i]s[i-1]c[i].g;memset(f,0x3f,sizeof(f));// 初始化DP数组为无穷大f[0][0]0;// 边界条件0个孩子分配0个糖果的怨气值为0for(inti1;in;i)// 枚举孩子数for(intji;jm;j)// 枚举糖果数至少要有i个糖果{// 情况1每人分一个糖果f[i][j]f[i][j-i];// 转移方程pre[i][j]{i,j-i};// 记录前驱状态// 情况2最后一批孩子分到额外的糖果for(intk0;ki;k)// 枚举上一批孩子的数量{// 计算从k个孩子扩展到i个孩子的最小怨气值if(f[i][j]f[k][j-(i-k)](s[i]-s[k])*k){f[i][j]f[k][j-(i-k)](s[i]-s[k])*k;pre[i][j]{k,j-(i-k)};// 记录前驱状态}}}coutf[n][m]endl;// 输出最小总怨气值print_path({n,m});// 回溯计算每个孩子的糖果数for(inti1;in;i)// 输出每个孩子分配的糖果数coutans[i] ;coutendl;return0;}【运行结果】3 20 1 2 3 2 6 7 7
