超详题解

没人发题解那我来发一个

看完题目
当然有些可爱的人要问了:这题好像可以用枚举

只能用二分(时间复杂度为 O(log n))
枚举(时间复杂度为 O(n^2))可能不止

当然有些大聪明又要问了:主播，主播那这道题怎么写

思路:排序 + 前缀和 + 二分查找，能正确求出最多雪橇数。

复杂度：O(N log N + Q log N)，满足题目要求

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll NM=2e5+5;//不大不小
ll n,a[NM],pre[NM],q;//每日养成好习惯
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    pre[0]=0;//细节
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    while(q--){
        ll query;//重点
        cin>>query;
        // 二分查找最大的 k 使得 pre[k] <= X
        int L=0,R=n,ans=0;
        while (L <= R) {
            int mid = (L + R) / 2;
            if (pre[mid]<=query) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }cout << ans << "\n";//细节\n性能更高
    }
    return 0;
}

真正简洁代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll NM=2e5+5;
ll n,a[NM],pre[NM],q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    pre[0]=0;
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    while(q--){
        ll query;
        cin>>query;
        ll ans=upper_bound(pre+1,pre+1+n,query)-pre;
        cout<<(ans-1)<<"\n";
    }
    return 0;
}

因为uppre_bound函数是查看>query的位置
减一就是查看<=query的位置了