Moe's CF Life

喵~ 主人，今天我们来帮一个商店老板解决一个棘手的定价问题，好让他的圣诞树能卖出最好的价钱捏！这就是 Codeforces 上的 2051E - Best Price 问题啦，我们一起来看看吧！

题目大意

一家商店新到了一批圣诞树，有 $n$ 位顾客前来选购。店长需要为圣诞树定一个统一的价格，目标是赚到最多的钱，但是有个小小的限制：收到的差评不能超过 $k$ 个。

对于每一位顾客（我们叫他顾客 $i$ 吧），我们知道两个关于他的数值 $a_i$ 和 $b_i$ ：

如果价格 p 小于或等于 $a_i$ ( $p \le a_i$ )，这位顾客会很开心地买下一棵树，并留下一个好评。
如果价格 p 大于 $a_i$ 但小于或等于 $b_i$ ( $a_i < p \le b_i$ )，这位顾客虽然还是会买，但会觉得有点小贵，于是会留下一个差评。
如果价格 p 大于 $b_i$ ( $p > b_i$ )，顾客就觉得太贵啦，转身就走，不买了。

我们的任务就是，帮店长找到一个最优的价格 p，使得总收入（也就是 价格 × 购买人数）最大，同时保证差评数量不超过 $k$ 个哦。

题解方法

主人请想一下，价格 p 可以是任何正整数，这范围也太大了喵！直接一个个试肯定是不行的。但是，我们可以发现一个小秘密~

购买的总人数和评价的好坏，只在价格 p 越过某个顾客的 $a_i$ 或 $b_i$ 时才会发生改变。比如说，如果价格从 5 涨到 6，但没有任何一个顾客的 $a_i$ 或 $b_i$ 是 5 或者 6，那么所有顾客的购买决策和评价都不会变。既然买的人数不变，那价格越高赚得越多呀！

这启发了我们：最优的价格 p 一定是某个顾客的 $a_i$ 或者 $b_i$ 。因为如果最优价格 p 不是任何一个 $a_i$ 或 $b_i$ ，我们总能稍微提高一点点价格，在不改变购买人数和差评数的情况下，获得更高的收益。直到价格碰到下一个 $a_j$ 或者 $b_j$ 为止。

所以，我们根本不需要检查所有可能的价格，只需要把所有顾客的 $a_i$ 和 $b_i$ 收集起来，作为我们的候选价格。这样，需要检查的价格数量最多就只有 $2n$ 个啦，问题是不是一下子就变得简单多了喵？

我们的策略就是：

把所有的 $a_i$ 和 $b_i$ 收集起来，形成一个候选价格列表。
对每个候选价格 p，计算出：
- 会有多少人购买。
- 会有多少人给差评。
如果差评数没有超过 $k$ ，就计算当前价格下的总收入，并更新我们的最大收入记录。
遍历完所有候选价格后，记录下的最大收入就是最终答案啦！

题解

好啦，现在我们来一步步实现这个思路，就像猫咪捕鼠一样，要有条不紊，喵~

第一步：收集和处理候选价格

我们创建一个列表 cand_prices，把所有输入的 $a_i$ 和 $b_i$ 都放进去。因为可能有重复的价格，所以我们先排序，然后用 std::unique 去掉重复项，让列表更清爽。

cpp

std::vector<int> cand_prices;
cand_prices.reserve(2 * n); // 预留空间，小优化~
for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
    cand_prices.push_back(a[i]);
}
for (int i = 0; i < n; ++i) {
    std::cin >> b[i];
    cand_prices.push_back(b[i]);
}

std::sort(cand_prices.begin(), cand_prices.end());
cand_prices.erase(std::unique(cand_prices.begin(), cand_prices.end()), cand_prices.end());

第二步：排序 a 和 b 数组

为了在计算时能快速地知道有多少人满足某个价格条件，我们最好先把输入的 a 数组和 b 数组也分别排个序。这样就可以使用二分查找啦，速度超快的说！

cpp

std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());

第三步：遍历候选价格并计算

现在，我们对每一个候选价格 p 进行检查。

cpp

long long max_earnings = 0; // 用 long long 防止收入太大溢出哦
for (int p : cand_prices) {
    // ... 计算过程 ...
}

对于一个价格 p：

计算购买人数 (buyers): 一个顾客会购买，只要价格 p 不超过他的预算上限 $b_i$ （即 $p \le b_i$ ）。因为 b 数组已经排好序了，我们可以用 std::lower_bound 飞快地找到第一个大于等于 p 的元素。从这个位置到数组末尾的所有顾客，他们的 $b_i$ 都大于等于 p，所以他们都会购买。
cpp
```
auto it_b = std::lower_bound(b.begin(), b.end(), p);
long long buyers = std::distance(it_b, b.end());
```
计算好评人数 (pos_rev): 一个顾客会给好评，只要价格 p 不超过他的心理价位 $a_i$ （即 $p \le a_i$ ）。同样地，我们在排好序的 a 数组里用 std::lower_bound 找到满足条件的人数。
cpp
```
auto it_a = std::lower_bound(a.begin(), a.end(), p);
long long pos_rev = std::distance(it_a, a.end());
```
计算差评人数 (neg_rev): 留下差评的顾客，是那些购买了但没有给好评的人。所以，差评人数就是 购买总人数 - 好评人数。
cpp
```
long long neg_rev = buyers - pos_rev;
```
检查约束并更新最大收益: 如果计算出的差评数 neg_rev 没有超过商店能承受的上限 k，那么这个价格 p 就是一个合法的方案。我们计算一下这个方案的总收入 (long long)p * buyers，然后和我们目前记录的最大收入 max_earnings 比较，取那个更大的值。
cpp
```
if (neg_rev <= k) {
    max_earnings = std::max(max_earnings, (long long)p * buyers);
}
```

第四步：输出结果

遍历完所有候选价格后，max_earnings 里存放的就是我们能找到的最大收入啦！把它打印出来就大功告成！

cpp

std::cout << max_earnings << "\n";

这样，我们就帮店长解决了大问题，可以开开心心卖圣诞树了喵！

知识点介绍

这个题目里用到了两个很有用的小技巧，主人可以学一下哦~

离散化 (Discretization) 这个思想是解决这道题的关键喵！当我们面对一个看似连续或者取值范围非常大的变量（比如本题的价格 p）时，如果问题的性质只依赖于这个变量和一些关键“阈值”的相对大小关系，我们就可以只考虑这些“阈值”作为变量的取值。这就叫离散化。在本题中，这些“阈值”就是所有顾客的 $a_i$ 和 $b_i$ 。通过只考虑这些点，我们把一个无限的搜索空间缩小到了一个大小为 $2n$ 的有限集合，让问题变得可以计算了。
二分查找 (Binary Search) 和 std::lower_bound 当我们需要在一个已排序的数组中快速查找某个元素，或者统计满足某种条件的元素数量时，二分查找是我们的不二之选，它的时间复杂度是 $O(\log n)$ , 非常高效！
- 二分查找：就像在一本很厚的、按页码排好序的书中找某一页。你不会一页一页翻，而是直接翻到中间，看页码是大了还是小了，然后决定在前半本书还是后半本书里继续找，每次都把搜索范围缩小一半。
- std::lower_bound：这是 C++ 标准库里的一个函数，它能帮我们在一个排好序的区间里，找到第一个不小于给定值的元素的位置。在本题解中，我们用它来快速计算出有多少个 $a_i$ 或 $b_i$ 是大于等于当前价格 p 的，非常方便的说！

主人学会了吗？下次遇到类似的问题，也要记得这些巧妙的思路哦，喵~

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍