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

文章目录

2025-7-14-C++ 学习排序（2）
P1059 [NOIP 2006 普及组] 明明的随机数
P1093 [NOIP 2007 普及组] 奖学金
P1781 宇宙总统
P2676 [USACO07DEC] Bookshelf B

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

排序，继续。

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

题目描述

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

输入格式

输入有两行，第 $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$ 行为一个正整数 $\le 300$ ，表示该校参加评选的学生人数。

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

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

提交代码

#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

输出 #1

4
1022356

说明/提示

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

$\leq n \leq 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 最近为奶牛们的图书馆添置了一个巨大的书架，尽管它是如此的大，但它还是几乎瞬间就被各种各样的书塞满了。现在，只有书架的顶上还留有一点空间。

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

输出 #1

说明/提示

输入说明：

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

输出说明：

一种只用 $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;
}

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

文章目录