【Leetcode Daily】2389和有限的最长子序列

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是求一个数组的每个值，与另一个数组子序列和的关系，在子序列和不超过这个值的前提下，求最长子序列的长度。

思路分享

• 前缀和+二分

  https://leetcode.cn/problems/longest-subsequence-with-limited-sum/solutions/1781111/fei-bao-li-zuo-fa-qian-zhui-he-er-fen-by-ny4m/

• 为了使得子序列长度越长，要尽可能选取数值较小的元素。所以先排序，然后用前缀和得到各个子序列的和。

• 具体实现中，前缀和用 numeric 库的 partial_sum 实现，而二分就直接用 ranges 库的 upper_bound 函数，之所以不用 lower_bound 是因为本题要求“不超过”，而非小于。当然，用加一值的lower_cound也行。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        ranges::sort(nums.begin(), nums.end()); // 排序
        partial_sum(nums.begin(), nums.end(), nums.begin()); // 前缀和
        for (int &q : queries) {
            //q = ranges::upper_bound(nums, q) - nums.begin();
            q = ranges::lower_bound(nums, q+1) - nums.begin();
        }
        return queries;
    }
};