题目 查找 数的个数 A-B 数对 拿钱 超市购物 儿童节分糖果 表达式括号匹配（升级版） 括号序列 第一个平手 鱼和熊掌
查找
题目大意
给定一个长度为 nnn 的非负整数序列 a1,a2,...,ana_1, a_2, ..., a_na1 ,a2 ,...,an ，该序列是单调不减的。接着给出 mmm 次询问，每次给出一个整数 qqq，询问该整数第一次在序列中出现的位置（下标从 1 开始）。若该数字未出现，输出 −1-1−1。
题意分析
本质是对一个单调不减数组执行 mmm 次查找操作，每次查找返回目标数在数组中第一次出现的位置。
由于数据规模大（n,m≤106n, m \leq 10^6n,m≤106），直接使用线性查找会超时，因此需使用二分查找加速查找过程。
解题思路
* 使用 C++ STL 中的 lower_bound 函数进行二分查找。
* lower_bound(begin, end, value) 返回第一个大于等于 value 的位置；
* 因为数组是单调不减的，所以第一次出现的位置一定是这个位置；
* 若 a[pos] == x，则找到了答案；
* 否则输出 -1。
* 注意数组从下标 1 开始，因此在使用 lower_bound 时，需使用 a + 1 到 a + n + 1。
* 由于输入输出数据量大，应使用 scanf 和 printf 替代 cin 和 cout 提高速度。
时间复杂度解析
* 构建数组时间复杂度为 O(n)O(n)O(n)；
* 每次查询使用二分查找，时间复杂度为 O(logn)O(\log n)O(logn)；
* 共 mmm 次查询，整体查询复杂度为 O(mlogn)O(m \log n)O(mlogn)；
* 总时间复杂度为 O(n+mlogn)O(n + m \log n)O(n+mlogn)，在 n,m≤106n, m \leq 10^6n,m≤106 的情况下能通过。
代码演示
数的个数
题目大意
给定一个长度为 nnn 的整数序列，再给出 mmm 个询问，每次给一个整数 numnumnum，要求输出该数在序列中出现的次数。
题意分析
对于每一个查询数字 numnumnum，我们要统计其在数组中出现了多少次。
数据范围较大，n,m≤105n, m \leq 10^5n,m≤105，若每次查询都遍历一遍数组，时间复杂度会达到 O(nm)O(nm)O(nm)，会超时。
因此需要使用二分查找进行优化。
解题思路
* 首先将原始数组排序；
* 然后每次使用 lower_bound 和 upper_bound：
* lower_bound(a, a + n, x)：找到第一个 大于等于 xxx 的位置；
* upper_bound(a, a + n, x)：找到第一个 大于 xxx 的位置；
* 两者之差就是 xxx 出现的次数；
* 由于每次查询时间复杂度为 O(logn)O(\log n)O(logn)，总复杂度为 O(nlogn+mlogn)O(n \log n + m \log n)O(nlogn+mlogn)。
时间复杂度解析
* 排序：O(nlogn)O(n \log n)O(nlogn)；
* 每次查询：O(logn)O(\log n)O(logn)，共 mmm 次；
* 总时间复杂度为 O(nlogn+mlogn)O(n \log n + m \log n)O(nlogn+mlogn)，在数据范围内可以通过。
代码演示
A-B 数对
题目大意
给定一个长度为 NNN 的正整数数组和一个正整数 CCC，求有多少对数 (A,B)(A, B)(A,B) 满足 A−B=CA - B = CA−B=C，其中 AAA 和 BBB 是数组中的两个元素，且可以来自不同位置（即使值相同也算作不同数对）。
题意分析
要求统计满足 A−B=CA - B = CA−B=C 的所有数对个数（下标不同即可），即对于每个 AiA_iAi ，找出数组中满足 B=Ai−CB = A_i - CB=Ai −C 的元素数量，并累加。
关键转换：
* 给定 AAA 和 CCC，我们可以唯一确定 B=A−CB = A - CB=A−C；
* 问题变为：对每一个 AiA_iAi ，统计数组中等于 Ai−CA_i - CAi −C 的数的个数。
解题思路
排序 + 二分查找
* 将数组升序排序；
* 遍历每一个元素 aia_iai ，计算 b=ai−Cb = a_i - Cb=ai −C；
* 在数组中用 lower_bound 和 upper_bound 查找 bbb 的个数；
* 所有找到的数对数量累加即为答案。
注意：即使有多个相同的数，也要统计所有可能位置组合。
时间复杂度解析
* 排序 + 二分版本：O(nlogn)O(n \log n)O(nlogn)；
代码演示
拿钱
题目大意
给定 nnn 种不同面值的货币，每种面值最多只能选一张，现在要从中选择 mmm 张纸币，问最多可以拿到多少钱。
题意分析
从 nnn 张不同面值的货币中选 mmm 张，使得这 mmm 张的面值之和最大。因为每种面值只能选一次，所以最优策略显然是：选最大的 mmm 个数相加。
解题思路
1. 输入所有面值；
2. 将这些面值从大到小排序；
3. 选择前 mmm 大的数，求和输出。
由于 n≤500n \leq 500n≤500，排序和遍历都非常高效。
时间复杂度解析
* 排序：O(nlogn)O(n \log n)O(nlogn)；
* 求和：O(m)O(m)O(m)；
* 总体：O(nlogn)O(n \log n)O(nlogn)，可轻松通过。
代码演示
超市购物
题目大意
给你 nnn 件商品，每件商品价格为 pip_ipi ，你有一张打x%折的折扣券和一张立减 y 元 的立减券，每件商品最多使用一张券。你要让所有商品中两件分别用掉这两张券，其余商品原价购买，使总花费最小。
题意分析
目标是：选两件商品分别用这两种券，使得这两张券使用后的总价格最小，其余商品用原价。
关键点：
* 折扣券：价格变成 pi×x100p_i \times \frac{x}{100}pi ×100x
* 立减券：价格变成 max(0,pi−y)\max(0, p_i - y)max(0,pi −y)
* 每件商品最多只能用一张券。
所以只需枚举价格最高的两件商品，尝试两种最优搭配方式（即哪件用哪种券），其余商品原价买入。
解题思路
1. 将商品按价格升序排序；
2. 设最后两个价格为 an−1,ana_{n-1}, a_nan−1 ,an ；
3. 枚举两种搭配方式：
* 情况1：an−1a_{n-1}an−1 用折扣券，ana_nan 用立减券；
* 情况2：ana_nan 用折扣券，an−1a_{n-1}an−1 用立减券；
4. 两种组合取最小值；
5. 剩下 n−2n-2n−2 件商品按原价加入总价；
6. 输出答案保留 12 位小数。
时间复杂度
* 排序：O(nlogn)O(n \log n)O(nlogn)
* 计算：O(n)O(n)O(n)
* 总体：O(nlogn)O(n \log n)O(nlogn)，可处理 n≤2×105n \leq 2 \times 10^5n≤2×105
代码演示
儿童节分糖果
题目大意
有 nnn 个小朋友排队，每人想要若干糖果。工作人员每次给每位排队小朋友固定 mmm 个糖果，如果糖果不够，则该小朋友继续排到队伍尾巴，直到每人都满足。求：
1. 最后一个离开队伍的小朋友编号
2. 一共发了多少糖果
题意分析
使用队列模拟整个分糖过程：
* 初始将每个小朋友编号依次入队；
* 每次从队头取出一个小朋友：
* 给他 mmm 个糖果，总糖果数累加；
* 如果还不满足，则重新入队尾；
* 直到队列为空。
关键点： 记录每次处理的是谁（编号 id），最后一个出队即为最后一个满足的小朋友。
解题思路
1. 使用队列 queue<int> 存放当前排队小朋友的编号；
2. 每次处理队头编号，扣除糖果；
3. 如果未满足，则重新排队；
4. 每次分糖，更新总糖果数；
5. 最后处理的 id 即为最后一个满意离开的孩子编号。
时间复杂度
* 每位小朋友最多入队 ⌈xim⌉\lceil \frac{x_i}{m} \rceil⌈mxi ⌉ 次；
* 总体复杂度 O(n⋅maxxim)O(n \cdot \frac{\max x_i}{m})O(n⋅mmaxxi )，对于数据范围是可以接受的。
代码演示
表达式括号匹配（升级版）
题目大意
给定一个以 @ 结尾的表达式，里面可能包含：
* 小写字母
* 运算符：+ - * /
* 括号：() 和 {}
你需要判断括号是否严格匹配（类型和顺序都要正确）。
题意分析
这是一道典型的括号匹配问题，需要用**栈（stack）**解决。
基本思路：
* 遇到左括号 ( 或 { 就入栈；
* 遇到右括号 ) 或 } 就判断栈顶是否为对应的左括号：
* 若匹配则出栈；
* 否则输出 NO；
* 处理结束后，如果栈非空，说明仍有未匹配的括号，也应输出 NO；
* 反之输出 YES。
解题思路
使用 STL 中的 stack<char> 来辅助括号的匹配：
1. 逐字符读入直到遇到终止符 @；
2. 遇到左括号入栈；
3. 遇到右括号时：
* 若栈为空或栈顶不匹配，则不合法；
* 否则匹配成功，出栈；
4. 表达式遍历结束后检查栈是否为空。
时间复杂度分析
* 每个字符最多压栈、弹栈一次；
* 总时间复杂度为 O(n)O(n)O(n)，其中 nnn 是表达式长度；
* 空间复杂度也是 O(n)O(n)O(n)。
代码演示
括号序列
题目大意
给定一个由 ( 和 ) 构成的长度为偶数的字符串，问最少修改多少个字符才能让这个括号序列变成一个合法的括号表达式。
合法的意思是括号成对，顺序正确匹配。
题意分析
题目并不是让你添加或删除字符，而是修改最少的字符数（把 ( 改成 ) 或 ) 改成 (），使其变成合法序列。
例如：
* 输入：()() → 本身合法 → 输出 0
* 输入：())( → 需要改两个字符 → 输出 2
解题思路
* 用一个 stack（栈）或一个整型变量 balance 来维护括号匹配情况；
* 当我们遇到 (，我们就让 balance++；
* 遇到 )，我们就让 balance--；
* 如果在过程中 balance < 0，说明右括号多了，这时候我们需要修改这个 ) 为 (（即 change++），然后让 balance++；
* 最后，balance 可能还大于 0，说明左括号多了（没被配对），每两个多余的 ( 需要修改一半（改为 )）来配对；
* 所以最终答案是：change + balance / 2
时间复杂度
* 时间复杂度：O(n)O(n)O(n)，只遍历一次字符串；
* 空间复杂度：O(1)O(1)O(1)，只使用常数变量。
代码演示
第一个平手
题目大意
给定一个升序排列的成绩序列（长度为 nnn），给出一个待查找的成绩 xxx，请找出第一个大于等于 xxx 的元素下标（从 0 开始计数）。
保证答案一定存在。
题意分析
这是一道标准的 二分查找模板题，要求我们找的是：
> 第一个满足 a[i] >= x 的下标 iii。
这正是 lower_bound() 在干的事情：
这个函数会返回 第一个 ≥ x 的位置。
解题思路
方法一：使用 lower_bound 函数
方法二：自己手写一个二分查找版本（更适合理解过程）
我们重点讲解手写版本：
* 定义左右边界 l = 0, r = n - 1
* 使用二分查找，更新 mid：
* 如果 a[mid] >= x，说明 mid 可能是答案，往左继续找，r = mid - 1
* 否则 a[mid] < x，往右边查找，l = mid + 1
* 最后返回的 l 即为最小的满足 a[i] >= x 的位置
时间复杂度
* 时间复杂度：O(logn)O(\log n)O(logn)
* 空间复杂度：O(1)O(1)O(1)
代码演示
鱼和熊掌
题目大意
有两组人编号：
* 第一个集合中有 nnn 个人得到了 鱼；
* 第二个集合中有 mmm 个人得到了 熊掌；
现在要求你输出 既在鱼组中也在熊掌组中的人的编号，顺序要按照鱼组中的顺序输出。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意分析
* 给定两个整数集合，输出它们的交集，但要求结果按第一个集合（鱼）中出现的顺序输出。
* 数据范围较大（n,m≤105n, m \le 10^5n,m≤105），要考虑效率。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解题思路
排序 + 二分查找
1. 将“熊掌”的编号排序；
2. 遍历“鱼”的编号，在“熊掌”中使用 lower_bound 查找是否存在；
3. 找到则输出。
适用条件：熊掌数组可排序，查找效率 O(logm)O(\log m)O(logm)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度分析
* 排序 + 二分：O(mlogm+nlogm)O(m \log m + n \log m)O(mlogm+nlogm)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码演示
