C++ 笔试刷题：排序子序列、消减整数与最长上升子序列

二、消减整数

题目解析

给定一个正整数 H，每次操作可以从 H 中减去 x 或 2*x。初始 x=1，第一次必须减去 1。目标是求将 H 减到 0 所需的最少次数。

算法思路

这是一个典型的贪心问题。为了让次数最少，我们应该尽可能多地减去较大的数。

核心策略：

1. 第一步：强制减去 1，此时 H 变为 H-1，x 保持为 1。
2. 后续步骤：在每一步中，检查剩余的 H 是否能被 2*x 整除。
   • 如果能整除，说明减去 2*x 更优，因为这样能更快接近 0，且不会导致剩余部分无法被整除（贪心性质）。此时更新 x *= 2。
   • 如果不能整除，则只能减去 x。
3. 终止条件：当 H 减至 0 时停止。

为什么优先选 2*x？ 如果 H 既是 x 的倍数也是 2*x 的倍数，显然减去更大的数 2*x 能让步数更少。如果 H 不是 2*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 > 0) {
            if (n % (2 * x) == 0) {
                x *= 2;
            }
            n -= x;
            ret++;
        }
        cout << ret << endl;
    }
    return 0;
}

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

题目解析

给定一个数组，找到其中最长的严格上升子序列的长度。要求时间复杂度优化至 O(n log n)。

算法思路

暴力解法通常是 O(n^2)，但通过维护一个辅助数组 dp，我们可以利用二分查找将复杂度降低。

关键观察：

1. 记录什么？ 我们不需要记录所有子序列的具体内容。对于长度为 k 的子序列，我们只需要记录其末尾元素的最小值。因为末尾元素越小，后续扩展的可能性越大。
2. 单调性： 随着子序列长度增加，其末尾元素的最小值也是非递减的。这保证了 dp 数组是有序的，可以使用二分查找。
3. 更新规则：
   • 如果当前元素 e 大于 dp 数组的最后一个元素，说明可以延长最长子序列，直接追加。
   • 否则，使用二分查找在 dp 中找到第一个大于等于 e 的位置，将其替换为 e。这意味着我们用更小的值更新了该长度的子序列末尾，为未来留出更多空间。

二分查找细节： 我们要找的是 dp 数组中第一个大于等于 e 的元素位置（左端点），用 lower_bound 的逻辑实现即可。

代码实现

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

以上三道题涵盖了数组遍历、贪心策略以及动态规划结合二分查找的经典考点。在实际面试或笔试中，注意边界条件的处理和代码的规范性往往比单纯写出算法更重要。