# 2389.和有限的最长子序列 (Easy)

## 问题描述
2389. 和有限的最长子序列 (Easy)

给你一个长度为 `n` 的整数数组 `nums` ，和一个长度为 `m` 的整数数组 `queries` 。

返回一个长度为 `m` 的数组 `answer`，其中 `answer[i]` 是 `nums` 中元素之和小于等于
`queries[i]` 的 **子序列** 的 **最大** 长度。

**子序列** 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

**示例 1：**

```
输入：nums = [4,5,2,1], queries = [3,10,21]
输出：[2,3,4]
解释：queries 对应的 answer 如下：
- 子序列 [2,1] 的和小于或等于 3 。可以证明满足题目要求的子序列的最大长度是 2 ，所以 answer[0]
= 2 。
- 子序列 [4,5,1] 的和小于或等于 10 。可以证明满足题目要求的子序列的最大长度是 3 ，所以
answer[1] = 3 。
- 子序列 [4,5,2,1] 的和小于或等于 21 。可以证明满足题目要求的子序列的最大长度是 4 ，所以
answer[2] = 4 。

```

**示例 2：**

```
输入：nums = [2,3,4,5], queries = [1]
输出：[0]
解释：空子序列是唯一一个满足元素和小于或等于 1 的子序列，所以 answer[0] = 0 。
```

**提示：**

- `n == nums.length`
- `m == queries.length`
- `1 <= n, m <= 1000`
- `1 <= nums[i], queries[i] <= 10⁶`

## 解题思路
由于子序列是删除任意元素得到的，因此我们可以对数组排序，不会对子序列的和产生影响；

然后求排序后的数组的前缀和，就能得到长为`l`的子序列的最小和；

然后遍历`queries`数组，对每个`queries[i]`，使用二分查找来找到最大的子序列长度。

## 代码
```cpp
class Solution {
  public:
    int Bfind(vector<int> &prefix, int target) {
        int left = 0, right = prefix.size();
        // 左闭右开
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefix[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    vector<int> answerQueries(vector<int> &nums, vector<int> &queries) {
        std::sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> prefix(n + 1);
        for (int i = 1; i <= n; ++i) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
        vector<int> res(queries.size());
        for (int i = 0; i < queries.size(); ++i) {
            res[i] = Bfind(prefix, queries[i] + 1) - 1;
        }
        return res;
    }
};
```