1 单选题（每题 2 分，共 30 分）
第 1 题 小杨想让指针 p 指向整数变量 x，正确写法是（ ）。
A. int p = &x;
B. int *p = x;
C. int *p = &x;
D. p = *x;
解析： 答案 C。正确声明指针：int *p = &x; 将指针 p 指向变量 x 的地址；输出变量值通过解引用 *p 实现。故选 C。
第 2 题 小杨写了如下的指针接力程序，程序执行完后变量 a、p1 和p2 的值分别是（ ）。
int a = 5; int* p1 = &a; int* p2 = p1; *p2 = 10;
A. 5 10 10 B. 5 10 15 C. 10 10 10 D. 5 5 10
解析： 答案 C。p1 为指向 a 的指针，p2 复制了 p1(指向同一地址)，对*p2 赋值等于对 a 赋值，*p1 也同值。所以 a、p1 和p2 的值分别是 10、10、10。故选 C。
第 3 题 小杨用一个二维数组表示棋盘，其中 1 表示有棋子，0 表示没有棋子。他想知道第 2 行第 3 列有没有棋子，可采用的代码是：（ ）。
int a[3][4] = {
{1, 0, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 0}
};
A. cout << a[1, 2] << endl;
B. cout << a[1][2] << endl;
C. cout << a(1, 2) << endl;
D. cout << a{1}{2} << endl;
解析： 答案 B。C++ 数组的下标是从 0 开始，第一个元素是 0 行 0 列，对第 2 行第 3 列表示为 a[1][2]。故选 B。
第 4 题 执行完下面的代码后，*(p + 5) 和 arr[1][1] 的值分别是（ ）。
int arr[3][4] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}}; int* p = &arr[0][0];
A. 5 6 B. 6 5 C. 5 5 D. 6 6
解析： 答案 D。C++ 二维数组是按行连续排的，p 指向 arr 的首地址，指向第一个元素，p+5 指向第 6 个元素，即 a[1][1]，*(p+5) 与 a[1][1] 同地址，输出 6 6。故选 D。
第 5 题 执行完下面的代码后，sum 的值是（ ）。
int arr[2][3][2] = {
{{1,2}, {3,4}, {5,6}},
{{7,8}, {9,10}, {11,12}}
}; int sum = 0; for(int i = 0; i < 2; i++)
for(int j = 0; j < 3; j++)
for(int k = 0; k < 2; k++)
if((i+j+k) % 2 == 0)
sum += arr[i][j][k];
A. 36 B. 39 C. 78 D. 30
解析： 答案 B。C++ 三维数组是按行连续排的，满足求和的条件是 i,j,k 分别为 0,0,0，0,1,1，0,2,0，1,0,1，1,1,0，1,2,1，1+4+5+8+9+12=39。故选 B。
第 6 题 执行完下面的代码后，输出是（ ）。
int a = 1; void test() {
int a = 2;
{
int a = 3;
a++;
}
a++;
cout << a << " ";
} int main() {
test();
cout << a;
return 0;
}
A. 3 1 B. 4 1 C. 3 2 D. 4 2
解析： 答案 A。第 1 行的 a 是全局变量，第 14 行调用 test() 函数，函数中有多个局部变量 a，第 4 行定义的局部变量 a=2，第 5~8 行中一对"{}"中定义 a 是局部变量，离开"}"就消失，恢复第 4 定义的 a，第 9 行的 a++ 执行的是第 4 行定义的 a，所以输出 3 和空格，第 15 行输出的是全局变量 a，值为 1。故选 A。
第 7 题 执行完下面的代码后，a、b 和 c 的值分别是（ ）。
void byValue(int x) { x = 100; } void byRef(int& x) { x = 200; } void byPointer(int* x) { *x = 300; } int main() {
int a = 1, b = 2, c = 3;
byValue(a);
byRef(b);
byPointer(&c);
return 0;
}
A. 100 200 300 B. 1 2 3 C. 1 200 300 D. 1 2 300
解析： 答案 C。byValue(int x) 是值传递，所以修改 x 不影响 a，a 仍为 1；byRef(int& x) 为引用传递，传递是变量地址，修改 x 等于修改 b，所以 b 为 200；byPointer(int* x) 为指针传递，x 指向 c 的地址。修改*x 等于修改 c，所以 c 为 300。a、b 和 c 的值分别是 1、200、300。故选 C。
第 8 题 运行如下代码会输出（ ）。
struct Point {
int x, y;
}; struct Rectangle {
Point topLeft;
Point bottomRight;
}; int main() {
Rectangle rect = {{10, 10}, {20, 20}};
rect.topLeft.x = 5;
Point* p = &rect.bottomRight;
p->y = 5;
cout << rect.topLeft.x + rect.bottomRight.y;
return 0;
}
A. 10 B. 30 C. 15 D. 20
解析： 答案 A。结构体定义：Point 包含 x,y；Rectangle 包含 topLeft,bottomRight。初始化：topLeft(10,10), bottomRight(20,20)。修改操作：topLeft.x=5, p->y=5。输出计算：5+5=10。故选 A。
第 9 题 给定函数 climbStairs(int n) 的定义如下，则 climbStairs(5) 的返回的值是（ ）。
int climbStairs(int n) {
if(n <= 2) return n;
int a = 1, b = 2;
for(int i = 3; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
A. 5 B. 8 C. 13 D. 10
解析： 答案 B。当 n=5 时：i=3 时，a=2，b=3；i=4，a=3，b=5；i=5 时，a=5，b=8。故选 B。
第 10 题 对如下 4 个扑克牌进行排序，
struct Card {
int value;
char suit; // 花色
}; Card cards[4] = {{5,'A'}, {3,'B'}, {5,'C'}, {3,'D'}};
使用某排序算法按 value 排序后，结果为：{3,'D'}, {3,'B'}, {5,'A'}, {5,'C'}，则这个排序算法是稳定的吗？
A. 稳定，因为相同 value 的元素相对顺序保持不变 B. 不稳定，因为 {3,'D'} 出现在 {3,'B'} 之前 C. 无法判断 D. 稳定，因为结果是有序的
解析： 答案 B。排序算法是否稳定，看同值排序时仍保持原次序的称稳定，否则称不稳定。由于按 value 排序，原{3,'B'}在{3,'D'}之前，{5,'A'}在{5,'C'}之前，稳定排序结果应该是{3,'B'},{3,'D'},{5,'A'},{5,'C'}，但结果是{3,'D'}, {3,'B'}, {5,'A'}, {5,'C'}，所以这个排序算法是不稳定的。故选 B。
第 11 题 下面的函数 selectTopK() 实现从 n 个学生中选出前 k 名成绩最好的学生颁发奖学金（不需要对所有学生完全排序，只需要找出前 k 名），则横线上应填写（ ）。
struct Student {
string name;
int score;
}; void selectTopK(Student students[], int n, int k) {
for (int i = 0; i < k; i++) {
int maxIdx = i;
for (____________________) { // 在此处填入代码
if (students[j].score > students[maxIdx].score) {
maxIdx = j;
}
}
if (maxIdx != i) {
Student temp = students[i];
students[i] = students[maxIdx];
students[maxIdx] = temp;
}
}
}
A. int j = 0; j < n; j++
B. int j = i + 1; j < n; j++
C. int j = i; j < n; j++
D. int j = 1; j <= n; j++
解析： 答案 B。程序的算法与选择排序类似：先取未排序区域 n 个数中的第 1 个数与后面 n-1 个进行比较，找到最大值，如最大值不是第 1 个则最大值与第 1 个数进行交换，这样最大值到了区域的第 1 个，再取第 2 个开始的区域，同样找区域中的最大，交换到第 2 个位置，以此类推，直到找到前 k 个最大值。所以循环变量 j 从 i+1 开始到 n-1(下标从 0 开始)，所以填 j=i+1; j<n; j++。故选 B。
第 12 题 某游戏的排行榜系统需要实时更新玩家分数。每次只有一个玩家的分数发生变化，排行榜已经是按分数降序排列的。现在需要将更新后的玩家调整到正确位置。下面的函数 updateRanking() 要实现上述功能，则两处横线上应分别填写（ ）。
struct Player {
string name;
int score;
}; // 玩家索引 playerIdx 的分数刚刚更新，需要调整位置 void updateRanking(Player players[], int size, int playerIdx) {
Player updatedPlayer = players[playerIdx];
if (playerIdx > 0 && updatedPlayer.score > players[playerIdx - 1].score) {
int i = playerIdx;
while (____________________) { // 在此处填入代码
players[i] = players[i - 1];
i--;
}
players[i] = updatedPlayer;
}
else if (playerIdx < size - 1 && updatedPlayer.score < players[playerIdx + 1].score) {
int i = playerIdx;
while (____________________) { // 在此处填入代码
players[i] = players[i + 1];
i++;
}
players[i] = updatedPlayer;
}
}
A.
i > 0 && updatedPlayer.score > players[i - 1].score
i < size - 1 && updatedPlayer.score < players[i + 1].score
B.
i < size - 1 && updatedPlayer.score < players[i + 1].score
i > 0 && updatedPlayer.score > players[i - 1].score
C.
i > 0 && updatedPlayer.score < players[i - 1].score
i < size - 1 && updatedPlayer.score < players[i + 1].score
D.
i > 0 && updatedPlayer.score < players[i - 1].score
i < size - 1 && updatedPlayer.score > players[i + 1].score
解析： 答案 A。程序的第 10 行判指定位置 (playerIdx) 的分数比上一位 (playerIdx-1) 高，则从 i 从 playerIdx 开始向上找直到 0(逆序最大值位置)，比较与上一位的分数，如仍大于则继续循环。所以 i>0(i-1>=0)，和 updatedPlayer.score > players[i - 1].score 同时成立，否则向后比较，比较与下一位的分数，如仍小于则继续循环。i<size-1(i+1<= size-1)，和 updatedPlayer.score < players[i + 1].score 同时成立。故选 A。
第 13 题 给定如下算法，其时间复杂度为（ ）。
bool f(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
sum += arr[j];
}
}
if (sum == target) return true;
}
return false;
}
A. O(n) B. O(n²) C. O(n³) D. O(2ⁿ)
解析： 答案 B。双重循环，循环次数都是 n，所以时间复杂度为 O(n²)。故选 B。
第 14 题 执行下面 C++ 程序，会输出（ ）。
int main() {
ofstream fout("test.txt");
fout << "Happy" << endl;
fout << "New Year";
fout.close();
ifstream fin("test.txt");
string s1, s2;
fin >> s1;
getline(fin, s2);
fin.close();
cout << s1 << "|" << s2;
return 0;
}
A. Happy|New Year B. Happy| New Year C. HappyNew Year| D. Happy|
解析： 答案 D。第 4 行写文件时加了换行 (endl)，所以写到文件为两行，第一行 Happy，第二行 NewYear。第 10 行读取时，fin >> s1 使用流提取操作符，按空白字符分割输入，读取连续非空白字符并存储到 string 对象 s1 中，会残留第一行的换行符。getline(fin, s2) 读取整行输入，包括空格，直至遇到换行符 (\n)，并将换行符从流中移除，结果存储到 s2。由于第 11 行读到的是换行 ('\n')，所以 s2 是空字符串。故选 D。
第 15 题 执行下面 C++ 代码，会输出 ( )。
int divide(int a, int b) {
if(b == 0) throw "Division by zero";
return a / b;
} int main() {
int result = 0;
try {
result = divide(10, 0);
cout << "A";
}
catch(const char* msg) {
cout << "B";
result = -1;
}
cout << result;
return 0;
}
A. A0 B. B-1 C. A10 D. 程序崩溃
解析： 答案 B。这是异常处理程序，调用 divide(int a, int b) 时，当 b=0 时抛出 "Division by zero" 异常。当主函数在 try 中运行 result = divide(10, 0); 时，因 b=0 会抛出异常，后面的 cout << "A" 不会被执行，抛出的异常要被 catch 子句接收处理，执行 cout << "B"，并给 result 赋 -1，第 16 行输出 result，所以输出结果为 B-1。故选 B。
2 判断题（每题 2 分，共 20 分）
第 1 题 小杨正在调试他的温度传感器程序，其中变量 x 保存当前温度。下面这段代码运行后，变量 x 的值变成了 8。
int x = 5; int *p = &x; *p = *p + 3;
解析： 答案√(正确)。p 为指向 x 的指针，*p 引用即 x，p+3，即 x+3，所以执行p = *p + 3; 后 x=5+3，x 变成 8。故正确。
第 2 题 一个结构体不能包含另一个结构体。
解析： 答案╳(错误)。一个结构体可以包含另一个结构体。故错误。
第 3 题 在 C++ 中，定义如下二维数组：int a[3][4];，数组 a 在内存中是按行优先连续存放的，即 a[0][0]、a[0][1]、a[0][2]、a[0][3] 在内存中是连续的。
解析： 答案√(正确)。C++ 二维数组同行数据连续存放，行与行也是连续存放。故正确。
第 4 题 执行下面程序后，变量 a 的值会变成 15。
void add(int &x){
x += 10;
} int a = 5; add(a);
解析： 答案√(正确)。函数 add(int &x) 为引用传递参数，实参 a 将地址传递形参 x，对 x 的修改就是对 a 的修改，因此执行 x += 10 之后，x 由 5 变为 15，并与 A 同地址，x 相当于是 a 的别名，a=15。故正确。
第 5 题 执行下面的 C++ 代码，会输出 8，因为两个指针地址相差 8 个字节（假设 int 占 4 字节）。
int arr[5] = {1, 2, 3, 4, 5}; int* p1 = arr; int* p2 = arr + 2; cout << p2 - p1; // 输出结果
解析： 答案╳(错误)。C++ 一维数组，数组名即为数组的首地址，所以 p1 是指向 arr 的指针。arr+2 为地址加，p2 指向后 2 个下标，指针之差是同对象内的'距离'，以'元素个数'为单位，而不是字节 p2-p1=2≠8，地址相差 2。故错误。
第 6 题 考虑用如下递推方式计算斐波那契数列，时间复杂度是 O(n)。
int n = 10; int f[20]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
解析： 答案√(正确)。程序只是单循环，时间复杂度为 O(n)。故正确。
第 7 题 冒泡排序和插入排序都是稳定排序算法。
解析： 答案√(正确)。冒泡排序和插入排序都是稳定排序。故正确。
第 8 题 下面这段代码实现了选择排序算法。
void sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int x = a[i];
int j = i - 1;
while (j >= 0 && a[j] > x) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = x;
}
}
解析： 答案╳(错误)。选择排序，涉及求最大值或最小值，程序中并没有。故错误。
第 9 题 下面代码可以正常编译并输出 10。
#include <iostream> using namespace std; int calculate(int x, int y = 10); int main() {
cout << calculate(5); // 调用 1
return 0;
} int calculate(int x, int y) {
return x * y;
} int calculate(int x) { // 重载函数
return x * 2;
}
解析： 答案╳(错误)。第 4 行函数声明中声明双参数，其中 y 默认为 10，calculate(5); 调用的并未调重载函数，而是按默认参数，双参数调用，x=5，y=10，返回 xy=510=50。故错误。
第 10 题 执行下面代码会输出 100。
int main() {
ofstream fout("data.txt");
fout << 10 << " " << 20 << endl;
fout << 30 << " " << 40;
fout.close();
ifstream fin("data.txt");
int a, b, c, d;
fin >> a >> b >> c >> d;
fin.close();
cout << a + b + c + d;
return 0;
}
解析： 答案√(正确)。第 3~4 行向文件写了两行，第一行 10 20 换行，第二行 30 40。fin 会丢掉前缀空白字符，一直读到空白字符 (不含空白字符)。a 读到的是 10，b 读到的是 20，c 读到的是 30，d 读到的是 40，所以结果为 10+20+30+40=100。故正确。
3 编程题（每题 25 分，共 50 分）
3.1 编程题 1
- 试题名称： 建造
- 时间限制： 1.0 s
- 内存限制： 512.0 MB
3.1.1 题目描述
小 A 有一张 M 行 N 列的地形图，其中第 i 行第 j 列的数字 aᵢⱼ代表坐标 (i, j) 的海拔高度。停机坪为一个 3×3 的区域且内部所有 9 个点的最大高度和最小高度之差不超过 H。
小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部 9 个点海拔之和最大是多少。
3.1.2 输入格式
第一行三个正整数 M, N, H，含义如题面所示。
之后 M 行，第 i 行包含 N 个整数，代表坐标 (i, j) 的高度。
数据保证总存在一个适合建造停机坪的区域。
3.1.3 输出格式
输出一行，代表最大的海拔之和。
3.1.4 样例
3.1.4.1 输入样例
5 5 3 5 5 5 5 5 5 1 5 1 5 5 5 5 5 5 5 2 5 2 5 3 5 5 5 2
3.1.4.2 输出样例
40
3.1.5 数据范围
对于所有测试点，保证 1≤M, N≤10³, 1≤H, aᵢⱼ≤10⁵。
3.1.6 编写程序
编程思路：
题目要求寻找一个 3×3 的区域，其中的最高海拔与最低海拔之差不超过 H，且 9 个点的海拔之和最大。如图 1 所示，以样例为例，M×N 的区域，选一 3×3 的区域，水平方向可移动 M-2 次，垂直方向可移动 N-2 次。只 3×3 的区域内的最高海拔与最低海拔之差不超过 H，就是一个有效区域，其海拔之和与当前最大海拔之和比较，两者大者作为当前最大海拔之和，最后输出即可。图 1 中黑色框中的 9 个海拔的最大海拔差为 4>H(=3)，不合适；黄底紫色框中的 9 个海拔的最大海拔差也是 4>H，不合适；红色框中的 9 个海拔的最大海拔差也是 3=H，合适，但是否是最大海拔之和要验证。
方法一：枚举法
枚举 3×3 的区域的左上角坐标，求以此点为左上角的 3×3 的区域中的各点海拔和、最高海拔、最低海拔。符合最高、最低海拔差有区域求最大海拔和。
参考程序代码如下：
#include <iostream>
using namespace std;
int a[1005][1005]; // M, N≤10³
int main() {
int M, N, H;
long long maxs = 0; // maxs 为 9 个点的最大海拔和
cin >> M >> N >> H;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
cin >> a[i][j]; // aᵢⱼ≤10⁵
for (int i = 0; i < M - 2; i++)
for (int j = 0; j < N - 2; j++) {
long long locs = 0; // 本区域海拔和，10³×10³个 10⁵数的和为 10¹¹级超过 int
int l_max = a[i][j], l_min = a[i][j]; // 区域最高、最低海拔，赋当前点海拔
for (int x = 0; x < 3; x++)
for (int y = 0; y < 3; y++) {
locs += a[i + x][j + y];
l_max = l_max > a[i + x][j + y] ? l_max : a[i + x][j + y];
l_min = l_min < a[i + x][j + y] ? l_min : a[i + x][j + y];
}
if (l_max - l_min <= H)
maxs = maxs > locs ? maxs : locs;
}
cout << maxs;
return 0;
}
方法二：
算法相同，3×3 区域的另一种表示，求最大、最小的另一种写法，程序更简洁一些。程序代码如下：
#include <iostream>
using namespace std;
int a[1005][1005]; // M, N≤10³
int main() {
int M, N, H;
long long maxs = 0; // maxs 为 9 个点的最大海拔和
cin >> M >> N >> H;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
cin >> a[i][j]; // aᵢⱼ≤10⁵
for (int i = 0; i < M - 2; i++)
for (int j = 0; j < N - 2; j++) {
long long locs = 0; // 本区域海拔和，10³×10³个 10⁵数的和为 10¹¹级超过 int
int l_max = a[i][j], l_min = a[i][j]; // 区域最高、最低海拔，赋当前点海拔
for (int x = i; x < i + 3; x++)
for (int y = j; y < j + 3; y++) {
locs += a[x][y];
if (a[x][y] > l_max) l_max = a[x][y];
if (a[x][y] < l_min) l_min = a[x][y];
}
if (l_max - l_min <= H)
if (locs > maxs) maxs = locs;
}
cout << maxs;
return 0;
}
3.2 编程题 2
- 试题名称： 优先购买
- 时间限制： 1.0 s
- 内存限制： 512.0 MB
3.2.1 题目描述
小 A 有 M 元预算。商店有 N 个商品，每个商品有商品名 S、价格 P 和优先级 V 三种属性，其中 V 为正整数，且越小代表商品的优先级越高。小 A 的购物策略为：
总是优先买优先级最高的东西； 如果有多个最高优先级商品，购买价格最低的； 如果有多个优先级最高且价格最低的商品，购买商品名字典序最小的。
小 A 想知道能购买哪些商品。
3.2.2 输入格式
第一行两个正整数 M, N，代表预算和商品数。
之后 N 行，每行一个商品，依次为 SᵢPᵢVᵢ，代表第 i 个商品的商品名、价格、优先级。
数据保证不存在两个名字相同的商品。
3.2.3 输出格式
按照字典序从小到大的顺序，输出所有购买商品的商品名。
3.2.4 样例
3.2.4.1 输入样例
20 4 apple 6 8 bus 15 1 cab 1 10 water 4 8
3.2.4.2 输出样例
bus cab water
3.2.5 数据范围
对于所有测试点，保证 1≤|Sᵢ|≤10, 1≤M, Pᵢ≤10⁵, 1≤N≤10³, 1≤Vᵢ≤10。商品名仅由小写字母组成且不存在两个相同的商品名。
3.2.6 参考程序
编程思路：
排序确保了购物策略的正确性 (先按优先级排 (升序)，同优先级按价格排 (升序)，优先级、同价格按商品名排 (升序，即字典序))，贪心选择在预算允许下尽可能购买商品，最终输出按字典序排列输出。排序用 STL 中的 sort() 函数。
方法一：
用结构体存储 M 个商品和购买商品的商品名称。参考程序代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005; // 最大商品数量
struct Node { // 定义商品结构体
string s; // 商品名称
int p, v; // 商品价格和优先级
} a[N], b[N]; // 存储所有商品和购买的商品
int m, n, cur;// m: 预算，n: 商品总数，cur：已购买商品数量
bool cmp(Node x, Node y) { // 排序次序：v(优先级) 升序 → p(价格) 升序 → s(名称) 字典序
if (x.v != y.v) return x.v < y.v; // 先按优先级升序排序
if (x.p != y.p) return x.p < y.p; // 优先级相同，按价格升序
return x.s < y.s; // 优先级和价格都相同，按商品名字典序
}
int main() {
cin >> m >> n; // 输入预算 m 和商品数量 n
for (int i = 0; i < n; i++) // 输入 n 个商品信息
cin >> a[i].s >> a[i].p >> a[i].v;
sort(a, a + n, cmp); // 排序，规则先按 v 升序，v 相同按 p 升序，v、p 都相同按 s 字典序
for (int i = 0; i < n; i++) { // 在预算范围内尽可能多地购买商品
if (m >= a[i].p) { // 预算足够
m -= a[i].p; // 扣除价格
b[cur++] = a[i]; // 将商品加入购买列表
}
}
sort(b, b + cur, [](const Node& a, const Node& b) {
return a.s < b.s; // 对购买的商品按名称字典序排序
});
for (int i = 0; i < cur; i++) { // 输出购买的商品名称
cout << b[i].s << endl;
}
return 0;
}
方法二：
由于输出只需输出购买商品的商品名称，为简化排序，购买商品的商品名称用字符串数组进行存储，M 个商品仍用结构体存储。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1005; // 最大商品数量
struct Node { // 定义商品结构体
string s; // 商品名称
int p, v; // 商品价格和优先级
} a[N]; // 存储所有商品
string b[N]; // 存储最终成功购买的商品名称
int m, n, cur;// m: 预算，n: 商品总，cur：已购买商品数量
bool cmp(Node x, Node y) { // 排序次序：v(优先级) 升序 → p(价格) 升序 → s(名称) 字典序
if (x.v != y.v) return x.v < y.v; // 先按优先级升序排序
if (x.p != y.p) return x.p < y.p; // 优先级相同，按价格升序
return x.s < y.s; // 优先级和价格都相同，按商品名字典序
}
int main() {
cin >> m >> n; // 输入预算 m 和商品数量 n
for (int i = 0; i < n; i++) // 输入 n 个商品信息
cin >> a[i].s >> a[i].p >> a[i].v;
sort(a, a + n, cmp); // 排序，规则先按 v 升序，v 相同按 p 升序，v、p 都相同按 s 字典序
for (int i = 0; i < n; i++) { // 在预算范围内尽可能多地购买商品
if (m >= a[i].p) { // 预算足够
m -= a[i].p; // 扣除价格
b[cur++] = a[i].s; // 将商品名称加入购买列表
}
}
sort(b, b + cur); // 对购买的商品按名称字典序排序
for (int i = 0; i < cur; i++) {// 输出购买的商品名称
cout << b[i] << endl;
}
return 0;
}
