P76034 饮品价格查询 — 题解

专题： 二分
适用题目： 新生 OJ 本地题包中的 P76034，不要直接用于外站同名题。

解题思路

价格升序排列后，对每个预算找第一个严格大于预算的位置，其下标就是不超过预算的商品数。

复杂度

排序 $O(n\log n)$，单次查询 $O(\log n)$。

易错点

等于预算的商品应当计入，所以寻找的是上界。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int cmp_ll_asc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (a > b) - (a < b);
}
int cmp_ll_desc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (b > a) - (b < a);
}

int upper_bound_ll(const long long *a,int n,long long x){
    int l=0,r=n;
    while(l<r){int mid=l+(r-l)/2;if(a[mid]<=x)l=mid+1;else r=mid;}
    return l;
}
int main(void) {
    int n,q;scanf("%d",&n);long long *a=malloc(n*sizeof(long long));
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    qsort(a,n,sizeof(long long),cmp_ll_asc);scanf("%d",&q);
    while(q--){long long x;scanf("%lld",&x);printf("%d\n",upper_bound_ll(a,n,x));}
    free(a);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n;
    vector<int>a(n);
    for(auto &x:a)cin>>x;
    sort(a.begin(),a.end());
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<upper_bound(a.begin(),a.end(),x)-a.begin()<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。