题解：学而思编程 递增

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】学而思编程递增【题目描述】现有数列A 1 , A 2 , ⋯ , A N A_1,A_2,⋯ ,A_NA1​,A2​,⋯,AN​修改最少的数字可以修改成小数使得数列严格单调递增。【输入】第1 11行1 11个整数N NN第2 22行N NN个整数A 1 , A 2 , ⋯ , A N A_1,A_2,⋯ ,A_NA1​,A2​,⋯,AN​【输出】1 11个整数表示最小修改的数字个数【输入样例】3 1 3 2【输出样例】1【核心思想】问题分析给定长度为N NN的数列要求修改最少的数字使得数列严格单调递增。等价于求最长上升子序列LIS因为保留的最多不修改的元素就是 LIS需要修改的元素个数为N − LIS长度 N - \text{LIS长度}N−LIS长度。算法选择贪心 二分优化维护数组b bbb [ i ] b[i]b[i]表示长度为i ii的上升子序列的最小结尾元素lower_bound使用二分查找找到第一个大于等于a [ i ] a[i]a[i]的位置关键步骤初始化l e n 0 len 0len0b [ 0 ] b[0]b[0]为极小值对于每个元素a [ i ] a[i]a[i]若a [ i ] b [ l e n ] a[i] b[len]a[i]b[len]则b [ l e n ] a [ i ] b[len] a[i]b[len]a[i]扩展 LIS否则用lower_bound找到位置m mm更新b [ m ] a [ i ] b[m] a[i]b[m]a[i]保持最小性答案N − l e n N - lenN−len总元素数减去 LIS 长度时间/空间复杂度时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)每个元素二分查找空间复杂度O ( N ) O(N)O(N)数组b bb和f ffLIS 贪心优化的核心思想转化思想最少修改次数 总元素数 - 最长不修改的元素个数LIS贪心策略同样长度的子序列结尾越小越有利于后续扩展二分查找利用b bb数组的单调性用lower_bound快速定位替换策略用更小的值替换保持b bb数组的最小性适用于最少修改/删除使序列递增的问题【算法标签】#线性DP-一维【代码详解】#includecstdio#includeiostream#includealgorithmusingnamespacestd;constintN100005;intn,a[N],b[N],f[N],maxn,len;// b: 最长递增序列, f: 每个元素所在的LIS长度intmain(){cinn;for(inti1;in;i){cina[i];// 输入序列}for(inti1;in;i){if(a[i]b[len])// 当前元素大于序列最后一个元素{b[len]a[i];// 扩展序列f[i]len;// 记录当前元素所在的LIS长度}else{// 找到第一个大于等于a[i]的位置intmlower_bound(b1,blen1,a[i])-b;b[m]a[i];// 替换该位置的元素f[i]m;// 记录当前元素所在的LIS长度}}coutn-len;// 输出最少需要删除的元素个数return0;}【运行结果】3 1 3 2 1