C++ 算法实战：排序子序列划分与 LIS 优化

二、消减整数

题目解析

给定一个正整数 H，从 1 开始减。第一次减去 1，之后每一次减去的数要么和上一次相等，要么是上一次的两倍。求最少需要几次才能将 h 减到 0。

解题思路

这是一个典型的贪心问题。我们的目标是让次数最少，所以每次减法应该尽可能大。

逻辑推导：

• 设当前步长为 x（初始为 1），剩余值为 n。
• 如果 n 是 2*x 的倍数，说明我们可以安全地减去 2*x 而不导致后续无法整除归零（或者说为了减少次数，优先选大的）。
• 如果 n 不是 2*x 的倍数，但可能是 x 的倍数，那就只能减去 x。
• 注意：题目要求第一次减去 1，所以初始 n 可以先减 1，步长 x 设为 1，计数 ret 设为 1。

代码实现

#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 log n)。

解题思路

暴力 DP 是 O(n^2)，无法满足要求。我们需要维护一个辅助数组 dp，其中 dp[i] 表示长度为 i+1 的上升子序列中，末尾元素的最小值。

核心优化：

1. 单调性：dp 数组本身是严格递增的。因为如果长度为 k 的子序列末尾最小值是 v，那么长度为 k+1 的子序列末尾一定大于 v。
2. 二分查找：当遍历到新元素 e 时，如果 e 大于 dp 中所有元素，直接追加到末尾，长度加一。否则，在 dp 中找到第一个大于等于 e 的位置，将其替换为 e。这样做的目的是让该长度的子序列末尾更小，有利于后续扩展。

代码实现

#include <vector>
using namespace std;

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;
    }
};

以上三道题涵盖了常见的贪心与动态规划优化技巧，建议结合具体数据范围多动手调试。