2025-7-14-C++ 学习 排序（2）

  排序，继续。

P1059 [NOIP 2006 普及组] 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N\le 100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数 $N$。

第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 $1$ 行为 $1$ 个正整数 $M$，表示不相同的随机数的个数。

第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入输出样例 #1

输入 #1

10
20 40 32 67 40 20 89 300 400 15

输出 #1

8
15 20 32 40 67 89 300 400

说明/提示

NOIP 2006 普及组 第一题

提交代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n;cin >> n;vector<int> numbers(n);for (int i = 0; i < n; i++) {cin >> numbers[i];}// 排序sort(numbers.begin(), numbers.end());// 去重vector<int> uniqueNumbers;if (!numbers.empty()) {uniqueNumbers.push_back(numbers[0]);for (int i = 1; i < n; i++) {if (numbers[i] != numbers[i - 1]) {uniqueNumbers.push_back(numbers[i]);}}}// 输出结果cout << uniqueNumbers.size() << endl;for (int num : uniqueNumbers) {cout << num << " ";}cout << endl;return 0;
}    

P1093 [NOIP 2007 普及组] 奖学金

题目背景

NOIP2007 普及组 T1

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 $5$ 名学生发奖学金。期末，每个学生都有 $3$ 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 $3$ 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 $5$ 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分) 是：

7 279  
5 279

这两行数据的含义是：总分最高的两个同学的学号依次是 $7$ 号、$5$ 号。这两名同学的总分都是 $279$ (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为 $7$ 的学生语文成绩更高一些。

如果你的前两名的输出数据是：

5 279  
7 279

则按输出错误处理，不能得分。

输入格式

共 $n+1$ 行。

第 $1$ 行为一个正整数 $n\le 300$，表示该校参加评选的学生人数。

第 $2$ 到 $n+1$ 行，每行有 $3$ 个用空格隔开的数字，每个数字都在 $0$ 到 $100$ 之间。第 $j$ 行的 $3$ 个数字依次表示学号为 $j-1$ 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 $1\sim n$（恰好是输入数据的行号减 $1$）。

保证所给的数据都是正确的，不必检验。

输出格式

共 $5$ 行，每行是两个用空格隔开的正整数，依次表示前 $5$ 名学生的学号和总分。

输入输出样例 #1

输入 #1

6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出 #1

6 265
4 264
3 258
2 244
1 237

输入输出样例 #2

输入 #2

8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出 #2

8 265
2 264
6 264
1 258
5 258

提交代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;struct Student {int id;int chinese;int math;int english;int total;
};// 自定义比较函数
bool compare(const Student& a, const Student& b) {if (a.total != b.total) {return a.total > b.total; // 总分高的优先}if (a.chinese != b.chinese) {return a.chinese > b.chinese; // 语文成绩高的优先}return a.id < b.id; // 学号小的优先
}int main() {int n;cin >> n;vector<Student> students(n);for (int i = 0; i < n; i++) {students[i].id = i + 1;cin >> students[i].chinese >> students[i].math >> students[i].english;students[i].total = students[i].chinese + students[i].math + students[i].english;}// 排序sort(students.begin(), students.end(), compare);// 输出前5名for (int i = 0; i < 5 && i < n; i++) {cout << students[i].id << " " << students[i].total << endl;}return 0;
}    

P1781 宇宙总统

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 $n$，代表竞选总统的人数。

接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。

输出格式

共两行，第一行是一个整数 $m$，为当上总统的人的号数。

第二行是当上总统的人的选票。

输入输出样例 #1

输入 #1

5
98765
12365
87954
1022356
985678

输出 #1

4
1022356

说明/提示

票数可能会很大，可能会到 $100$ 位数字。

$1\le n\le 20$。

提交代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;// 比较两个大数字字符串的大小
bool isGreater(const string& a, const string& b) {if (a.length() != b.length()) {return a.length() > b.length();}return a > b;
}int main() {int n;cin >> n;string maxVote = "";int maxIndex = 0;for (int i = 1; i <= n; i++) {string vote;cin >> vote;if (isGreater(vote, maxVote)) {maxVote = vote;maxIndex = i;}}cout << maxIndex << endl;cout << maxVote << endl;return 0;
}    

P2676 [USACO07DEC] Bookshelf B

题目描述

Farmer John 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

所有 $N(1\le N\le 20,000)$ 头奶牛都有一个确定的身高 $H_i(1\le H_i\le 10,000)$。设所有奶牛身高的和为 $S$。书架的高度为 $B$，并且保证 $1\le B\le S<2,000,000,007$。

为了够到比最高的那头奶牛还要高的书架顶，奶牛们不得不像演杂技一般，一头站在另一头的背上，叠成一座“奶牛塔”。当然，这个塔的高度，就是塔中所有奶牛的身高之和。为了往书架顶上放东西，所有奶牛的身高和必须不小于书架的高度。

显然，塔中的奶牛数目越多，整座塔就越不稳定，于是奶牛们希望在能够到书架顶的前提下，让塔中奶牛的数目尽量少。现在，奶牛们找到了你，希望你帮她们计算这个最小的数目。

输入格式

• 第 $1$ 行：2 个用空格隔开的整数：$N$ 和 $B$；
• 第 $2\dots N+1$ 行：第 $i+1$ 行是 $1$ 个整数：$H_i$。

输出格式

• 第 $1$ 行：输出 $1$ 个整数，即最少要多少头奶牛叠成塔，才能够到书架顶部。

输入输出样例 #1

输入 #1

6 40
6
18
11
13
19
11

输出 #1

3

说明/提示

输入说明：

一共有 $6$ 头奶牛，书架的高度为 $40$，奶牛们的身高在 $6\dots 19$ 之间。

输出说明：

一种只用 $3$ 头奶牛就达到高度 $40$ 的方法：$18+11+13$。当然还有其他方法，在此不一一列出了。

提交代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {int n, b;cin >> n >> b;vector<int> heights(n);for (int i = 0; i < n; i++) {cin >> heights[i];}// 从大到小排序sort(heights.begin(), heights.end(), greater<int>());int sum = 0;int count = 0;// 贪心策略：优先选择最高的奶牛for (int height : heights) {sum += height;count++;if (sum >= b) {break;}}cout << count << endl;return 0;
}