Moe's CF Life

喵~ 主人，今天我们来看一道非常有趣的题目，就像在琳琅满目的商店里挑选最爱的小鱼干一样喵！这道题是 Codeforces 上的 "Interesting drink"，我们一起来看看怎么解决它吧！

题目大意

这道题是说，有一个叫 Vasiliy 的程序员小哥，他特别喜欢喝一种叫做 "Beecola" 的饮料，喵~ 城市里有 n 家商店卖这种饮料，每家店的价格都不同，分别是 x_1, x_2, ..., x_n。

Vasiliy 计划连续 q 天去买饮料。在第 i 天，他身上有 m_i 个硬币。他想知道，在每一天，他手里的钱足够在多少家商店里买到一瓶 "Beecola" 呢？

简单来说，就是给了 n 个价格和 q 个询问。对于每个询问的钱数 m，我们要找出有多少个价格 x_i 是小于或等于 m 的。

举个例子喵：商店价格是 [3, 10, 8, 6, 11]。

第一天有 1 块钱，买不起任何一家店的饮料，所以答案是 0。
第二天有 10 块钱，可以买得起价格为 3, 10, 8, 6 的四家店的饮料，所以答案是 4。
第三天有 3 块钱，只能买得起价格为 3 的那家店，所以答案是 1。
第四天有 11 块钱，所有店的饮料都买得起，所以答案是 5。

题解方法

看到这道题，最直接的想法是什么喵？当然是对于每一天的钱 m，都去遍历一遍所有 n 家商店的价格，看看有几家是 ≤ m 的。

但是我们来看看数据范围：n 和 q 最大都可以到 100,000。如果用这种暴力的方法，时间复杂度就是 O(n * q)，也就是 10^5 * 10^5 = 10^10，这运算量也太大了，计算机会累坏的，肯定会超时的喵！Vasiliy 可等不了那么久！

所以我们需要一个更聪明的办法。这个问题其实是在问：“对于一个给定的数 m，在一个数组中有多少个数小于等于它？”

这种问题有一个经典的优化思路！如果数组是有序的，查找就会变得非常快。

所以我们的方法是：

排序：先把所有商店的价格 x 从小到大排个序。这一步的时间复杂度是 O(n log n)。
二分查找：对于每一天给定的钱数 m，我们在排好序的价格数组里进行二分查找。我们要找的不是一个特定的值，而是所有小于等于 m 的商店的数量。这恰好是最后一个价格小于等于 m 的商店的位置（或者说，第一个价格大于 m 的商店的位置）。

利用二分查找，每次查询的时间复杂度就从 O(n) 降到了 O(log n)。

总的时间复杂度就是 O(n log n) (排序) + O(q log n) (q次查询)，这个速度就非常快了，完全可以通过这道题，喵~

题解

下面就是这道题的 C++ 代码啦，让本喵来给你详细解释一下每一部分都在做什么吧！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 这是一个加速魔法喵，让 C++ 的输入输出变得飞快！
    // 在处理大量数据时非常有用，是个好习惯。
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;
    std::vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> x[i];
    }

    // 这是解题的关键第一步！
    // 把所有商店的价格从小到大排个队，整整齐齐的喵。
    // 这样我们后面才能愉快地使用二分查找。
    std::sort(x.begin(), x.end());

    int q;
    std::cin >> q;
    while (q--) {
        int m;
        std::cin >> m;
        
        // 这里就是最核心的魔法啦！
        // std::upper_bound 会在排好序的数组中，找到第一个严格大于 m 的元素的位置。
        // 比如价格是 [3, 6, 8, 10, 11]，m 是 10。
        // upper_bound(10) 会找到 11 的位置。
        auto it = std::upper_bound(x.begin(), x.end(), m);
        
        // it 是一个指向那个位置的“指针”（迭代器）。
        // 用它减去数组的起始位置 x.begin()，得到的就是这个位置的下标。
        // 这个下标值，正好就是所有小于或等于 m 的元素的数量！
        // 比如上面那个例子，11 的下标是 4，说明有 4 个元素 (3, 6, 8, 10) 小于等于 10。
        // 是不是很神奇喵？
        std::cout << (it - x.begin()) << "\n";
    }

    return 0;
}

知识点介绍

这道题主要用到了两个非常重要的知识点，本喵给你介绍一下~

1. 二分查找 (Binary Search)

二分查找是一种在有序数组中查找某一特定元素的搜索算法。它的工作原理就像猜数字游戏一样喵！

首先，从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束。
如果目标值大于中间元素，则在数组大于中间元素的那一半中查找。
如果目标值小于中间元素，则在数组小于中间元素的那一半中查找。
每一次比较都使搜索范围缩小一半，所以效率非常高，时间复杂度是 O(log n)。

对于这道题，我们不是查找一个精确的值，而是查找一个“边界”，二分查找同样能胜任！

2. `std::upper_bound`

std::upper_bound 是 C++ 标准模板库（STL）中的一个函数，它封装了二分查找的逻辑，用起来非常方便。

功能：std::upper_bound(first, last, val) 会在指定的有序范围 [first, last) 内，返回一个迭代器，指向第一个严格大于 val 的元素。
为什么它很适合这道题：我们想知道有多少个价格 x_i 小于或等于 m。在一个从小到大排好序的数组里，所有小于等于 m 的元素都会排在所有大于 m 的元素前面。upper_bound 帮我们找到了第一个大于 m 的元素的分界线。这个分界线的位置（也就是它的下标），正好就是前面所有小于等于 m 的元素的总数。

还有一个和它很像的函数叫 std::lower_bound，它找的是第一个大于或等于 val 的元素。这两个函数是二分查找问题的好帮手，主人要好好记住它们哦！

好啦，今天的题解就到这里啦，希望对主人有帮助喵~ 下次再见！

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

1. 二分查找 (Binary Search) ​

2. std::upper_bound ​

题目大意

题解方法

题解

知识点介绍

1. 二分查找 (Binary Search)

2. `std::upper_bound`