有基础班_第八课_第一次月测
2025-06-05 13:25:34
发布于：上海
34阅读
0回复
0点赞
| 题目 |
|---|
| 查找 |
| 数的个数 |
| A-B 数对 |
| 拿钱 |
| 超市购物 |
| 儿童节分糖果 |
| 表达式括号匹配（升级版） |
| 括号序列 |
| 第一个平手 |
| 鱼和熊掌 |
查找
题目大意
给定一个长度为 的非负整数序列 ，该序列是单调不减的。接着给出 次询问，每次给出一个整数 ，询问该整数第一次在序列中出现的位置（下标从 1 开始）。若该数字未出现，输出 。
题意分析
本质是对一个单调不减数组执行 次查找操作，每次查找返回目标数在数组中第一次出现的位置。
由于数据规模大（），直接使用线性查找会超时，因此需使用二分查找加速查找过程。
解题思路
- 使用 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提高速度。
时间复杂度解析
- 构建数组时间复杂度为 ；
- 每次查询使用二分查找，时间复杂度为 ；
- 共 次查询，整体查询复杂度为 ；
- 总时间复杂度为 ，在 的情况下能通过。
代码演示
#include <iostream>
#include <algorithm> // for lower_bound
#include <cstdio> // for scanf, printf
using namespace std;
const int maxn = 1e6 + 9; // 定义最大数组长度
int n, m, a[maxn], x;
int main() {
// 输入 n 和 m
scanf("%d %d", &n, &m);
// 输入数组 a，从下标 1 开始
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
// 对每个查询执行二分查找
while (m--) {
scanf("%d", &x);
// 使用 lower_bound 查找第一个大于等于 x 的位置
int pos = lower_bound(a + 1, a + n + 1, x) - a;
// 判断该位置的元素是否等于 x
if (a[pos] == x)
printf("%d ", pos); // 输出位置
else
printf("-1 "); // 未找到
}
return 0;
}
数的个数
题目大意
给定一个长度为 的整数序列，再给出 个询问，每次给一个整数 ，要求输出该数在序列中出现的次数。
题意分析
对于每一个查询数字 ，我们要统计其在数组中出现了多少次。
数据范围较大，，若每次查询都遍历一遍数组，时间复杂度会达到 ，会超时。
因此需要使用二分查找进行优化。
解题思路
- 首先将原始数组排序；
- 然后每次使用
lower_bound和upper_bound：lower_bound(a, a + n, x)：找到第一个 大于等于 的位置；upper_bound(a, a + n, x)：找到第一个 大于 的位置；- 两者之差就是 出现的次数；
- 由于每次查询时间复杂度为 ，总复杂度为 。
时间复杂度解析
- 排序：；
- 每次查询：，共 次；
- 总时间复杂度为 ，在数据范围内可以通过。
代码演示
#include <iostream>
#include <algorithm> // 包含 lower_bound 和 upper_bound
using namespace std;
const int maxn = 1e5 + 9;
int n, m, a[maxn], x;
int main() {
// 输入数组长度 n
cin >> n;
// 输入 n 个数到数组 a 中（从下标 1 开始）
for (int i = 1; i <= n; i++)
cin >> a[i];
// 对数组进行排序，方便使用二分查找
sort(a + 1, a + n + 1);
// 输入查询次数 m
cin >> m;
while (m--) {
// 输入查询数字 x
cin >> x;
// 使用 upper_bound 和 lower_bound 查找 x 的个数
int pos1 = lower_bound(a + 1, a + n + 1, x) - a; // 第一个 >= x 的位置
int pos2 = upper_bound(a + 1, a + n + 1, x) - a; // 第一个 > x 的位置
// 两者之差即为 x 的个数
cout << pos2 - pos1 << endl;
}
return 0;
}
A-B 数对
题目大意
给定一个长度为 的正整数数组和一个正整数 ，求有多少对数 满足 ，其中 和 是数组中的两个元素，且可以来自不同位置（即使值相同也算作不同数对）。
题意分析
要求统计满足 的所有数对个数（下标不同即可），即对于每个 ，找出数组中满足 的元素数量，并累加。
关键转换：
- 给定 和 ，我们可以唯一确定 ；
- 问题变为：对每一个 ，统计数组中等于 的数的个数。
解题思路
排序 + 二分查找
- 将数组升序排序；
- 遍历每一个元素 ，计算 ；
- 在数组中用
lower_bound和upper_bound查找 的个数； - 所有找到的数对数量累加即为答案。
注意：即使有多个相同的数，也要统计所有可能位置组合。
时间复杂度解析
- 排序 + 二分版本：；
代码演示
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 9;
int n, c, a[maxn], sum;
int main() {
// 输入数组长度 n 和目标差值 c
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> a[i];
// 对数组进行排序，方便后续二分查找
sort(a + 1, a + n + 1);
// 枚举数组中的每一个数作为 A
for (int i = 1; i <= n; i++) {
int b = a[i] - c; // 计算 B = A - C
// 在有序数组中查找 B 的出现次数
int pos1 = lower_bound(a + 1, a + n + 1, b) - a;
int pos2 = upper_bound(a + 1, a + n + 1, b) - a;
sum += pos2 - pos1; // 累加满足条件的数对个数
}
// 输出答案
cout << sum;
return 0;
}
拿钱
题目大意
给定 种不同面值的货币，每种面值最多只能选一张，现在要从中选择 张纸币，问最多可以拿到多少钱。
题意分析
从 张不同面值的货币中选 张，使得这 张的面值之和最大。因为每种面值只能选一次，所以最优策略显然是：选最大的 个数相加。
解题思路
- 输入所有面值；
- 将这些面值从大到小排序；
- 选择前 大的数，求和输出。
由于 ，排序和遍历都非常高效。
时间复杂度解析
- 排序：；
- 求和：；
- 总体：，可轻松通过。
代码演示
#include <bits/stdc++.h>
using namespace std;
const int maxn = 509; // 最多 500 种货币
int a[maxn];
bool cmp(int x, int y) {
return x > y; // 降序排序
}
int main() {
int n, m;
cin >> n >> m;
// 输入面值
for (int i = 1; i <= n; i++)
cin >> a[i];
// 从大到小排序
sort(a + 1, a + n + 1, cmp);
// 选前 m 个最大的面值
int sum = 0;
for (int i = 1; i <= m; i++)
sum += a[i];
cout << sum;
return 0;
}
超市购物
题目大意
给你 件商品，每件商品价格为 ，你有一张打x%折的折扣券和一张立减 y 元 的立减券，每件商品最多使用一张券。你要让所有商品中两件分别用掉这两张券，其余商品原价购买，使总花费最小。
题意分析
目标是：选两件商品分别用这两种券，使得这两张券使用后的总价格最小，其余商品用原价。
关键点：
- 折扣券：价格变成
- 立减券：价格变成
- 每件商品最多只能用一张券。
所以只需枚举价格最高的两件商品，尝试两种最优搭配方式（即哪件用哪种券），其余商品原价买入。
解题思路
- 将商品按价格升序排序；
- 设最后两个价格为 ；
- 枚举两种搭配方式：
- 情况1： 用折扣券， 用立减券；
- 情况2： 用折扣券， 用立减券；
- 两种组合取最小值；
- 剩下 件商品按原价加入总价；
- 输出答案保留 12 位小数。
时间复杂度
- 排序：
- 计算：
- 总体：，可处理
代码演示
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 200009;
int a[maxn];
int main() {
int n, x, y;
cin >> n >> x >> y;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1); // 从小到大排序
// 设最后两件商品分别用两种优惠券
double opt1 = a[n - 1] * x * 0.01 + max(0, a[n] - y); // a[n-1]打折, a[n]立减
double opt2 = a[n] * x * 0.01 + max(0, a[n - 1] - y); // a[n]打折, a[n-1]立减
double res = min(opt1, opt2); // 两种搭配取最小
for (int i = 1; i <= n - 2; i++) {
res += a[i]; // 其余商品原价
}
printf("%.12f\n", res);
return 0;
}
儿童节分糖果
题目大意
有 个小朋友排队，每人想要若干糖果。工作人员每次给每位排队小朋友固定 个糖果，如果糖果不够，则该小朋友继续排到队伍尾巴，直到每人都满足。求：
- 最后一个离开队伍的小朋友编号
- 一共发了多少糖果
题意分析
使用队列模拟整个分糖过程：
- 初始将每个小朋友编号依次入队；
- 每次从队头取出一个小朋友：
- 给他 个糖果，总糖果数累加；
- 如果还不满足，则重新入队尾；
- 直到队列为空。
关键点： 记录每次处理的是谁（编号 id），最后一个出队即为最后一个满足的小朋友。
解题思路
- 使用队列
queue<int>存放当前排队小朋友的编号； - 每次处理队头编号，扣除糖果；
- 如果未满足，则重新排队；
- 每次分糖，更新总糖果数；
- 最后处理的
id即为最后一个满意离开的孩子编号。
时间复杂度
- 每位小朋友最多入队 次；
- 总体复杂度 ，对于数据范围是可以接受的。
代码演示
#include <iostream>
#include <queue>
using namespace std;
int x[109]; // 存储每个孩子还需要的糖果数量
int main() {
int n, m;
cin >> n >> m; // n 个小朋友，每次发 m 个糖果
for (int i = 1; i <= n; i++) {
cin >> x[i]; // 每个小朋友初始想要的糖果
}
queue<int> q;
for (int i = 1; i <= n; i++) {
q.push(i); // 按编号顺序排队
}
int sum = 0; // 总共发出的糖果数
int id = 0; // 最后一个离开的孩子编号
while (!q.empty()) {
id = q.front();
q.pop();
sum += m;
x[id] -= m;
if (x[id] > 0) {
q.push(id); // 没满足继续排队
}
}
cout << id << " " << sum << endl;
return 0;
}
表达式括号匹配（升级版）
题目大意
给定一个以 @ 结尾的表达式，里面可能包含：
- 小写字母
- 运算符：
+-*/ - 括号：
()和{}
你需要判断括号是否严格匹配（类型和顺序都要正确）。
题意分析
这是一道典型的括号匹配问题，需要用**栈（stack）**解决。
基本思路：
- 遇到左括号
(或{就入栈； - 遇到右括号
)或}就判断栈顶是否为对应的左括号：- 若匹配则出栈；
- 否则输出
NO；
- 处理结束后，如果栈非空，说明仍有未匹配的括号，也应输出
NO； - 反之输出
YES。
解题思路
使用 STL 中的 stack<char> 来辅助括号的匹配：
- 逐字符读入直到遇到终止符
@； - 遇到左括号入栈；
- 遇到右括号时：
- 若栈为空或栈顶不匹配，则不合法；
- 否则匹配成功，出栈；
- 表达式遍历结束后检查栈是否为空。
时间复杂度分析
- 每个字符最多压栈、弹栈一次；
- 总时间复杂度为 ，其中 是表达式长度；
- 空间复杂度也是 。
代码演示
#include <iostream>
#include <stack>
using namespace std;
int main() {
string s;
getline(cin, s); // 读取整行表达式
stack<char> st;
for (int i = 0; i < s.length(); i++) {
char ch = s[i];
if (ch == '@') break; // 表达式终止
if (ch == '(' || ch == '{') {
st.push(ch); // 左括号入栈
} else if (ch == ')') {
// 判断是否匹配并出栈
if (st.empty() || st.top() != '(') {
cout << "NO" << endl;
return 0;
}
st.pop();
} else if (ch == '}') {
if (st.empty() || st.top() != '{') {
cout << "NO" << endl;
return 0;
}
st.pop();
}
}
// 栈是否为空决定最终答案
if (st.empty())
cout << "YES" << endl;
else
cou << "NO" << endl;
return 0;
}
括号序列
题目大意
给定一个由 ( 和 ) 构成的长度为偶数的字符串，问最少修改多少个字符才能让这个括号序列变成一个合法的括号表达式。
合法的意思是括号成对，顺序正确匹配。
题意分析
题目并不是让你添加或删除字符，而是修改最少的字符数（把 ( 改成 ) 或 ) 改成 (），使其变成合法序列。
例如：
- 输入：
()()→ 本身合法 → 输出0 - 输入：
())(→ 需要改两个字符 → 输出2
解题思路
- 用一个
stack（栈）或一个整型变量balance来维护括号匹配情况； - 当我们遇到
(，我们就让balance++； - 遇到
)，我们就让balance--； - 如果在过程中
balance < 0，说明右括号多了，这时候我们需要修改这个)为(（即change++），然后让balance++； - 最后，
balance可能还大于 0，说明左括号多了（没被配对），每两个多余的(需要修改一半（改为)）来配对； - 所以最终答案是：
change + balance / 2
时间复杂度
- 时间复杂度：，只遍历一次字符串；
- 空间复杂度：，只使用常数变量。
代码演示
#include <iostream>
using namespace std;
int main() {
string s;
cin >> s;
int balance = 0; // 当前括号平衡值
int change = 0; // 需要修改的次数
for (int i = 0; i < s.length(); i++) {
char ch = s[i];
if (ch == '(') {
balance++; // 多了一个左括号
} else { // ch == ')'
balance--; // 尝试匹配一个左括号
if (balance < 0) {
// 说明没有左括号来匹配当前这个右括号，需要修改
change++; // 把当前这个右括号修改为左括号
balance += 2; // 修改为左括号，相当于 +2
}
}
}
// 剩下的 balance 是多余的左括号，每两个配一个右括号
change += balance / 2;
cout << change << endl;
return 0;
}
第一个平手
题目大意
给定一个升序排列的成绩序列（长度为 ），给出一个待查找的成绩 ，请找出第一个大于等于 的元素下标（从 0 开始计数）。
保证答案一定存在。
题意分析
这是一道标准的 二分查找模板题，要求我们找的是：
第一个满足
a[i] >= x的下标 。
这正是 lower_bound() 在干的事情：
int pos = lower_bound(a, a + n, x) - a;
这个函数会返回 第一个 ≥ 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的位置
时间复杂度
- 时间复杂度：
- 空间复杂度：
代码演示
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
cin >> x;
int pos = lower_bound(a.begin(), a.end(), x) - a.begin();
cout << pos << endl;
return 0;
}
鱼和熊掌
题目大意
有两组人编号：
- 第一个集合中有 个人得到了 鱼；
- 第二个集合中有 个人得到了 熊掌；
现在要求你输出 既在鱼组中也在熊掌组中的人的编号，顺序要按照鱼组中的顺序输出。
题意分析
- 给定两个整数集合，输出它们的交集，但要求结果按第一个集合（鱼）中出现的顺序输出。
- 数据范围较大（），要考虑效率。
解题思路
排序 + 二分查找
- 将“熊掌”的编号排序；
- 遍历“鱼”的编号，在“熊掌”中使用
lower_bound查找是否存在； - 找到则输出。
适用条件：熊掌数组可排序，查找效率 。
时间复杂度分析
- 排序 + 二分：
代码演示
#include<iostream>
#include<algorithm>
using namespace std;
int n, m;
int fish[100010], bear[100010];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> fish[i];
for (int i = 1; i <= m; i++)
cin >> bear[i];
sort(bear + 1, bear + m + 1); // 从 bear[1] 到 bear[m] 排序
for (int i = 1; i <= n; i++) {
// lower_bound 查找第一个 ≥ fish[i] 的位置
int pos = lower_bound(bear + 1, bear + 1 + m, fish[i]) - bear;
if (bear[pos] == fish[i]) {
cout << fish[i] << " ";
}
}
return 0;
}
有帮助，赞一个