C++ 算法实战：排序子序列、消减整数与最长上升子序列

二、消减整数

题目解析

给定一个正整数 H，从 1 开始进行减法操作。第一次减去 1，之后每一次减去的数要么是上一次减去的数 x，要么是 2*x。目标是求将 H 减到 0 所需的最少次数。

简单来说，每次操作可以选择减去 x 或 2x，其中 x 初始为 1，随后根据选择更新。

算法思路

暴力解法 尝试所有可能的组合，直到 H 减到 0 或小于 0。这种方法时间复杂度和空间复杂度都过高，且容易陷入死循环或无法恰好减到 0 的情况。

贪心优化 既然要求最少次数，直觉上我们应该尽可能多地减去较大的数。但前提是减完后剩余部分能被整除，否则可能无法精确减到 0。

具体策略如下：

1. 首先执行一次减法，H 变为 H-1，已用次数为 1，当前基数 x=1。
2. 在后续步骤中，检查剩余的 H 是否能被 2*x 整除。
   • 如果能整除，说明减去 2*x 是可行的，且能更快接近 0。此时我们将 x 翻倍，然后减去新的 x。
   • 如果不能整除，说明减去 2*x 会导致余数无法被后续操作消除，只能减去当前的 x。

这个逻辑保证了每一步都在'可行'的前提下最大化了减去的幅度。

代码实现

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        n--; // 第一次减去 1
        int ret = 1, x = 1;
        while (n) {
            if (n % (2 * x) == 0) {
                x *= 2;
            }
            n -= x;
            ret++;
        }
        cout << ret << endl;
    }
    return 0;
}

三、最长上升子序列 (二)

题目解析

给定一个数组，找到其中最长的严格上升子序列的长度。严格上升意味着新数组中的元素必须严格大于前一个元素。

算法思路

动态规划思路 直观的想法是记录每个位置作为结尾的最长上升子序列长度。但这需要 O(n^2) 的时间复杂度，对于大数据量不够高效。

核心优化 我们不需要记录所有的子序列，只需要记录长度为 n 的子序列中，末尾元素最小的那个值。为什么？因为末尾元素越小，后续接上更大元素的概率就越大，越容易形成长度更长的序列。

假设我们维护一个数组 dp，其中 dp[i] 表示长度为 i+1 的上升子序列的最小末尾元素。这个 dp 数组本身也是严格递增的。

二分查找 当遍历到一个新元素 e 时：

1. 如果 e 大于 dp 中所有元素，说明它可以接在最长子序列后面，形成更长的序列，直接追加到 dp 末尾。
2. 如果 e 不能延长最长序列，但它比某个长度的子序列末尾小，我们可以替换掉那个位置的末尾元素，从而让该长度的子序列变得更'优'。

由于 dp 数组是有序的，我们可以使用二分查找来定位应该替换的位置。我们要找的是第一个大于等于 e 的元素位置，将其替换为 e。

代码实现

class Solution {
public:
    int dp[100001];
    int pos = 0;

    int LIS(vector<int>& a) {
        for (auto& e : a) {
            if (pos == 0 || e >= dp[pos]) {
                dp[++pos] = e;
            } else {
                int l = 1, r = pos;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (dp[mid] >= e) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                dp[l] = e;
            }
        }
        return pos;
    }
};