A611. 午餐吃什么 —— 详细题解

一、题意简述

给你 n 种外卖，每种外卖有三个属性：

• 名字（字符串，不含空格）
• 价格（整数）
• 受欢迎程度（整数）

你手上有 m 块钱，只能买一份外卖，且价格不能超过 m。在所有买得起的外卖中，选出受欢迎程度最大的那一份输出。

题目保证：可选的最大受欢迎程度的外卖只有一个（即不会出现并列第一的情况）。

如果任何一份都买不起，输出 ...>_<...。

---

二、解题思路

这是一道非常经典的线性扫描 / 遍历求最大值问题。

核心步骤：

1. 读入数据：把每种外卖的名字、价格、受欢迎程度分别存到数组中。
2. 遍历筛选：依次检查每一种外卖，如果它的价格 ≤ m（买得起），就拿它的受欢迎程度和当前记录的最大值比较。
3. 更新最优解：如果当前外卖的受欢迎程度严格大于已记录的最大值，就更新最大值，并记录下标。
4. 输出结果：
   • 遍历结束后，如果最大值仍然是初始值 -1，说明没有任何一份买得起，输出 ...>_<...。
   • 否则，输出记录下来的那份外卖的名字、价格和受欢迎程度。

为什么用 b = -1 作为初始值？

因为题目保证受欢迎程度是正整数（> 0），所以用 -1 作为初始"最大值"可以确保：

• 只要遇到任何一份买得起的外卖，它的受欢迎程度一定 > -1，一定会被更新。
• 遍历结束后如果 b 还是 -1，就说明一份都没买得起。

---

三、代码详解

#include <bits/stdc++.h>
using namespace std;

string s[100005];   // 存储外卖名字
int p[100005];      // 存储外卖价格
int l[100005];      // 存储外卖受欢迎程度

int main() {
    int n, m;
    cin >> n >> m;

    // 读入 n 种外卖的信息
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> p[i] >> l[i];
    }

    int b = -1;  // 记录当前找到的最大受欢迎程度，初始为 -1 表示"还没找到任何买得起的"
    int a = 0;   // 记录最大受欢迎程度对应的外卖下标

    // 遍历所有外卖，筛选出买得起且最受欢迎的
    for (int i = 1; i <= n; i++) {
        if (p[i] <= m && l[i] > b) {  // 买得起 且 受欢迎程度比当前最大值还大
            b = l[i];  // 更新最大值
            a = i;     // 记录下标
        }
    }

    // 判断是否有买得起的外卖
    if (b == -1) {
        cout << "...>_<..." << endl;
    } else {
        cout << s[a] << " " << p[a] << " " << l[a] << endl;
    }

    return 0;
}

逐行说明：

代码	说明
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

输入：
4 16
宫保鸡丁盖饭 10 10
鱼香肉丝盖饭 15 16
芹菜水饺 14 18
猪肝面 18 9

遍历过程：

下标 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

输入：
4 5
宫保鸡丁盖饭 10 10
鱼香肉丝盖饭 15 16
芹菜水饺 14 18
猪肝面 18 9

所有外卖价格都 > 5，全部跳过，b 始终为 -1，输出：...>_<... ✅

---

五、复杂度分析

• 时间复杂度：$O(n)$，只需要遍历一次数组。
• 空间复杂度：$O(n)$，存储三个数组。

对于题目给定的数据范围（$n < 20$），这个复杂度绰绰有余，甚至 $n$ 到 $10^5$ 级别也能轻松通过。

---

六、易错点 & 注意事项

1. 名字不含空格：题目用 cin >> 读入名字，说明名字中间没有空格。如果名字有空格，需要用 getline。
2. 下标从 1 开始：代码中数组下标从 1 开始，注意不要越界或漏掉。
3. 严格大于 >：条件写的是 l[i] > b 而不是 >=，因为题目保证最大值唯一，写 > 或 >= 都能 AC，但 > 更符合"保证唯一"的题意。
4. 初始值设为 -1：不能用 0，因为如果受欢迎程度可以是 0 就会出错（虽然本题保证是正整数，但养成好习惯很重要）。

---

七、拓展思考

如果题目不保证最大值唯一，要求输出所有并列第一的外卖，该怎么做？

可以先遍历一遍找出最大值 maxVal，再遍历一遍把所有 价格≤m 且 受欢迎程度==maxVal 的外卖都输出。