本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing273. 分级 - AcWing题库【题目描述】给定长度为N NN的序列A AA构造一个长度为N NN的序列B BB满足B BB非严格单调即B 1 ≤ B 2 ≤ … ≤ B N B_1≤B_2≤…≤B_NB1≤B2≤…≤BN或B 1 ≥ B 2 ≥ … ≥ B N B_1≥B_2≥…≥B_NB1≥B2≥…≥BN。最小化S ∑ i 1 N ∣ A i − B i ∣ S\sum_{i1}^N|A_i−B_i|S∑i1N∣Ai−Bi∣。只需要求出这个最小值S SS。【输入】第一行包含一个整数N NN。接下来N NN行每行包含一个整数A i A_iAi。【输出】输出一个整数表示最小S SS值。【输入样例】7 1 3 2 4 5 3 9【输出样例】3【算法标签】#线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;constintN2005,INF1e9;intn,a[N],A[N];// n: 元素个数a: 原始数组A: 排序后的数组intf[N][N];// DP数组f[i][j]表示处理到第i个元素以A[j]作为第i个元素的最小代价intsolve(){for(inti1;in;i)// 遍历原始数组的每个元素{intpminINF;// 记录上一行中的最小值for(intj1;jn;j)// 遍历排序后数组的每个元素{pminmin(pmin,f[i-1][j]);// 更新上一行的最小值f[i][j]pminabs(a[i]-A[j]);// 状态转移方程}}intresINF;// 初始化结果为最大值for(inti1;in;i)// 遍历最后一行resmin(res,f[n][i]);// 找到最小代价returnres;}intmain(){cinn;// 输入元素个数for(inti1;in;i)// 输入原始数组{cina[i];A[i]a[i];// 复制到A数组用于排序}sort(A1,An1);// 对A数组进行升序排序intanssolve();// 第一次求解非递减情况reverse(A1,An1);// 反转A数组得到降序序列ansmin(ans,solve());// 第二次求解非递增情况取较小值coutansendl;// 输出结果return0;}【运行结果】7 1 3 2 4 5 3 9 3
