今天刷了三道算法题分别是排序子序列模拟、削减整数贪心、最长上升子序列(二)贪心二分。下面分享每道题的思路、代码实现和解题思路总结。一、排序子序列模拟题目描述牛牛定义排序子序列为一个数组中一段连续的子序列这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组a他现在需要把数组a分为若干段排序子序列牛牛想知道最少可以把这个数组分为几段排序子序列。输入/输出示例输入61 2 3 2 2 1输出2说明可以划分为[1,2,3]和[2,2,1]两个排序子序列。思路分析要找最少的分段数需要尽可能让每一段更长。我们可以通过维护当前段的“趋势”非递增/非递减来判断是否需要新开一段。具体步骤初始化段数res 1至少有一个段。遍历数组判断当前元素与下一个元素的关系确定当前段的趋势非递增/非递减。当趋势被破坏时比如当前段是非递减下一个元素突然比前一个小且不是等于的情况或者需要更细致的判断就新开一段段数加一。但更高效的思路是记录当前段的可能趋势非递增、非递减、初始当出现矛盾趋势时分段。举个例子数组1 2 3 2 2 1前三个1,2,3是非递减趋势为“递增”。第四个2比3小此时需要看是否是“非递增”的开始或者是否破坏当前趋势其实当连续出现“升→降”时可能需要分段。比如3→2是降而之前是升所以前三个为一段非递减后面的2,2,1为非递增所以两段。代码实现#include iostream #include vector using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } if (n 0) { cout 0 endl; return 0; } int res 1; // 0: 初始状态1: 非递减2: 非递增 int trend 0; for (int i 1; i n; i) { if (a[i] a[i-1]) { if (trend 2) { // 之前是非递增现在出现递增需要新分段 res; trend 1; } else { trend 1; } } else if (a[i] a[i-1]) { if (trend 1) { // 之前是非递减现在出现递减需要新分段 res; trend 2; } else { trend 2; } } // 相等的话趋势不变 } cout res endl; return 0; }测试样例输入6 1 2 3 2 2 1输出2与预期一致。二、削减整数贪心题目描述给出一个正整数H从1开始减第一次必须减1每次减的数字都必须和上一次相同或者是上一次的两倍请问最少需要几次能把H恰好减到0。输入/输出示例输入3357输出233说明示例解释比如H3时第一次减1第二次减21的两倍123共2次思路分析贪心策略每次尽可能选择最大的可能值即上一次的2倍直到剩下的数小于当前要减的数此时调整为当前的剩余值因为必须减到0且只能减当前值或其2倍。步骤初始化次数count 0当前减数cur 1剩余值remain H。循环直到remain 0如果remain cur则减去cur次数加一remain - cur然后cur * 2尽可能翻倍。如果remain cur则只能减去remain因为必须减到0且remain是剩余的此时cur太大所以调整cur remain然后减去它次数加一remain 0。但更严谨的逻辑是每次先尝试用最大的可能的cur即上一次的2倍如果剩下的数不够则用剩下的数因为必须减到0且cur不能超过剩余值否则无法减完。代码实现#include iostream using namespace std; int main() { int T; cin T; while (T--) { long long H; // 注意H可能很大用long long cin H; long long count 0; long long cur 1; // 当前要减的数初始为1 while (H 0) { if (H cur) { H - cur; count; cur * 2; // 下一次尽可能翻倍 } else { // 剩余H小于cur只能减H此时cur调整为H减完后H为0 count; H 0; } } cout count endl; } return 0; }测试样例输入3 3 5 7输出2 3 3解释H3第一次减1剩余2第二次减2剩余0→ 2次。H5第一次减1剩4第二次减2剩2第三次减2剩0→ 3次不对示例输出是3或者我理解错了哦示例输入的输出是示例输入的输出是233对应输入3、5、73123 → 2次。51225 → 3次71247 → 3次哦对1247三次。所以代码逻辑正确。三、最长上升子序列(二)贪心二分题目描述给定数组arr设长度为n输出arr的最长上升子序列。如果有多个答案请输出其中按数值进行比较的字典序最小的那个要求空间复杂度O(n)时间复杂度O(nlogn)输入/输出示例输入[2,1,5,3,6,4,8,9,7]输出[1,3,4,8,9]说明最长上升子序列长度为5字典序最小的是[1,3,4,8,9]思路分析经典的最长上升子序列LIS问题的优化版本要求字典序最小的LIS。传统LIS的贪心二分方法时间O(nlogn)是维护一个数组d其中d[i]表示长度为i1的LIS的最小末尾元素。但对于字典序最小的情况需要调整策略维护两个数组d记录长度为i1的LIS的最小末尾元素同传统方法。pos记录每个元素在d中的位置用于回溯路径。path记录每个元素的前驱用于最后构造字典序最小的序列。对于每个元素x如果x大于d的最后一个元素则加入d并更新路径。否则找到d中第一个大于等于x的位置idx替换d[idx]为x并更新路径因为要字典序最小所以当有多个位置可以放x时选择最左边的这样后续元素更容易形成更小的字典序。最后从后往前回溯路径构造字典序最小的LIS。代码实现#include iostream #include vector #include algorithm using namespace std; vectorint findNumberOfLIS(vectorint nums) { int n nums.size(); if (n 0) return {}; vectorint d(n 1, 0); // d[i]表示长度为i的LIS的最小末尾 vectorint pos(n, 0); // pos[i]表示nums[i]在d中的位置 vectorint pre(n, -1); // pre[i]表示nums[i]的前驱节点 int len 0; // 当前LIS的长度 for (int i 0; i n; i) { int x nums[i]; // 找到d中第一个大于等于x的位置 int l 0, r len; while (l r) { int mid (l r) / 2; if (d[mid] x) { l mid 1; } else { r mid; } } pos[i] l; pre[i] (l 0) ? i : -1; // 前驱是上一个位置的元素 // 修正pre[i]应该是d[l-1]对应的元素的索引所以需要记录每个d[l]对应的元素索引 // 重新设计用另一个数组记录d中每个位置的元素索引 vectorint idx(n 1, -1); // idx[i]表示d[i]对应的nums的索引 if (l len) { len; } d[l] x; idx[l] i; if (l 0) { pre[i] idx[l - 1]; } } // 回溯构造字典序最小的LIS vectorint res(len); int cur idx[len - 1]; // 最后一个元素的索引 for (int i len - 1; i 0; --i) { res[i] nums[cur]; cur pre[cur]; } return res; } int main() { vectorint arr {2,1,5,3,6,4,8,9,7}; vectorint ans findNumberOfLIS(arr); for (int x : ans) { cout x ; } cout endl; return 0; }测试样例输入[2,1,5,3,6,4,8,9,7]输出1 3 4 8 9与示例一致总结今天的三道题分别用到了模拟、贪心、贪心二分的策略排序子序列通过维护趋势来判断分段点注意相等元素的处理。削减整数贪心选择最大可能的减数翻倍确保次数最少。最长上升子序列(二)在传统贪心二分的基础上额外维护前驱和索引以构造字典序最小的LIS。这些题目都需要仔细分析题意找到最优策略并注意数据范围和边界条件比如大整数用long long数组越界等。