一、题意简述
给你 n 种外卖,每种外卖有三个属性:
* 名字(字符串,不含空格)
* 价格(整数)
* 受欢迎程度(整数)
你手上有 m 块钱,只能买一份外卖,且价格不能超过 m。在所有买得起的外卖中,选出受欢迎程度最大的那一份输出。
题目保证:可选的最大受欢迎程度的外卖只有一个(即不会出现并列第一的情况)。
如果任何一份都买不起,输出 ...>_<...。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、解题思路
这是一道非常经典的线性扫描 / 遍历求最大值问题。
核心步骤:
1. 读入数据:把每种外卖的名字、价格、受欢迎程度分别存到数组中。
2. 遍历筛选:依次检查每一种外卖,如果它的价格 ≤ m(买得起),就拿它的受欢迎程度和当前记录的最大值比较。
3. 更新最优解:如果当前外卖的受欢迎程度严格大于已记录的最大值,就更新最大值,并记录下标。
4. 输出结果:
* 遍历结束后,如果最大值仍然是初始值 -1,说明没有任何一份买得起,输出 ...>_<...。
* 否则,输出记录下来的那份外卖的名字、价格和受欢迎程度。
为什么用 B = -1 作为初始值?
因为题目保证受欢迎程度是正整数(> 0),所以用 -1 作为初始"最大值"可以确保:
* 只要遇到任何一份买得起的外卖,它的受欢迎程度一定 > -1,一定会被更新。
* 遍历结束后如果 b 还是 -1,就说明一份都没买得起。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、代码详解
逐行说明:
代码 说明 string s[100005] 用字符串数组存外卖名字,下标从 1 开始 int p[100005] 价格数组 int l[100005] 受欢迎程度数组(变量名 l 是 level/liked 的缩写) cin >> n >> m 读入外卖种数 n 和预算 m for (int i = 1; i <= n; i++) 循环读入每种外卖的三个属性 int b = -1, a = 0 b 记录最大受欢迎程度,a 记录对应下标 if (p[i] <= m && l[i] > b) 两个条件同时满足:①价格不超过预算 ②受欢迎程度比当前记录的大 b = l[i]; a = i;
更新最优解 if (b == -1) 如果遍历完还是 -1,说明没有买得起的
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、样例模拟
样例 1
遍历过程:
下标 i 名字 价格 受欢迎程度 价格≤16? 受欢迎程度>当前b? 操作 1 宫保鸡丁盖饭 10 10 ✅ 10 > -1 ✅ b=10, a=1 2 鱼香肉丝盖饭 15 16 ✅ 16 > 10 ✅ b=16, a=2 3 芹菜水饺 14 18 ✅ 18 > 16 ✅ b=18, a=3 4 猪肝面 18 9 ❌ — 跳过
最终 b=18, a=3,输出:芹菜水饺 14 18 ✅
样例 2
所有外卖价格都 > 5,全部跳过,b 始终为 -1,输出:...>_<... ✅
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、复杂度分析
* 时间复杂度:O(n)O(n)O(n),只需要遍历一次数组。
* 空间复杂度:O(n)O(n)O(n),存储三个数组。
对于题目给定的数据范围(n<20n < 20n<20),这个复杂度绰绰有余,甚至 nnn 到 10510^5105 级别也能轻松通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、易错点 & 注意事项
1. 名字不含空格:题目用 cin >> 读入名字,说明名字中间没有空格。如果名字有空格,需要用 getline。
2. 下标从 1 开始:代码中数组下标从 1 开始,注意不要越界或漏掉。
3. 严格大于 >:条件写的是 l[i] > b 而不是 >=,因为题目保证最大值唯一,写 > 或 >= 都能 AC,但 > 更符合"保证唯一"的题意。
4. 初始值设为 -1:不能用 0,因为如果受欢迎程度可以是 0 就会出错(虽然本题保证是正整数,但养成好习惯很重要)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、拓展思考
如果题目不保证最大值唯一,要求输出所有并列第一的外卖,该怎么做?
> 可以先遍历一遍找出最大值 maxVal,再遍历一遍把所有 价格≤m 且 受欢迎程度==maxVal 的外卖都输出。