题解归档 - cf600B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf600B
• 本地来源：problems/cf600B/idea.md
• 题目链接：https://codeforces.com/contest/600/problem/B
• 原始标题：cf600B — Queries about less or equal elements

思路

cf600B — Queries about less or equal elements

题意

对每个 b_j 统计 a 中有多少个元素 ≤ b_j。

做法

排序 a，upper_bound 得 ≤ 的个数。

结论

O((n+m) log n)。

代码

来源：problems/cf600B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:14:49
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=200005;
ll n,m,i,j,k,a[maxn+5],b[maxn+5];
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(i=1;i<=m;i++){
        cin>>b[i];
        k=upper_bound(a+1,a+1+n,b[i])-a-1;
        if(i>1) cout<<" ";
        cout<<k;
    }
    cout<<endl;
    return 0;
}