C++ 笔试算法实战：排序子序列与贪心策略详解

消减整数

问题描述

给定正整数 H，每次减去 x（初始为 1）。下一次减去的数可以是 x 或 2*x。求将 H 减到 0 的最少次数。

思路分析

目标是让次数最少，这意味着每次减去的数越大越好。

1. 贪心选择：如果当前剩余的 H 是 2x 的倍数，那么减去 2x 肯定比减去 x 更优，因为步长更大且能整除。
2. 特殊情况：如果 H 不是 2*x 的倍数，但可能是 x 的倍数，此时只能减去 x。
3. 流程：第一次强制减去 1（即 x=1），之后循环判断是否能被 2*x 整除，决定更新 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;
            } else {
                n -= x;
            }
            ret++;
        }
        cout << ret << endl;
    }
    return 0;
}

最长上升子序列 (二)

问题描述

给定数组，求最长严格上升子序列的长度。要求时间复杂度为 O(n log n)。

思路分析

这是经典的 LIS 问题，暴力 DP 是 O(n^2)，需要优化。

1. 维护状态：定义 dp[len] 表示长度为 len 的上升子序列中，末尾元素的最小值。
2. 单调性：显然，长度越长的子序列，其末尾元素的最小值不会更小，因此 dp 数组是非递减的。
3. 二分查找：遍历数组元素 num：
   • 如果 num 大于 dp 中所有元素，说明可以接在最长子序列后面，扩展长度。
   • 否则，找到 dp 中第一个大于等于 num 的位置，用 num 替换它。这样做的目的是让该长度的子序列末尾更小，有利于后续扩展。
4. 结果：dp 数组的有效长度即为答案。

代码实现

#include <vector>
#include <algorithm>
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 {
                // 二分查找第一个 >= e 的位置
                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;
    }
};