LeetCode 2389. 和有限的最长子序列
原题链接
简单
作者:
α_29
,
2023-03-17 16:50:37
,
所有人可见
,
阅读 122
排序+前缀和+二分
调用upper_bound()函数(原理是二分)
//求序列可以排序
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(),nums.end());
int n = nums.size();
int s[n+1];
s[0] = 0;
for(int i = 1; i <= n; i ++ ) s[i] = s[i-1] + nums[i - 1];
vector<int> res;
for(auto x:queries){
//upper_bound(start,end,x) end表示数组结束地址的下一位
int l = upper_bound(s + 1,s + n + 1,x) - s;//二分查找
res.push_back(l - 1);
}
return res;
}
};
手动写二分
class Solution {
public:
vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
sort(nums.begin(),nums.end());
int n = nums.size();
int s[n+1];
s[0] = 0;
for(int i = 1; i <= n; i ++ ) s[i] = s[i-1] + nums[i - 1];
vector<int> res;
for(auto x:queries){
int l = 1, r = n;
while(l < r){
int mid = (l + r) >> 1;
if(s[mid] >= x) r = mid;
else l = mid + 1;
}
//此时l可能在x 左边 或 右边 或 x本身
if(s[l] > x)
res.push_back(l - 1);
else if(s[l] <= x)
res.push_back(l);
}
return res;
}
};