PTA L1-8 静静的推荐

分数 20

全屏浏览题目

切换布局

作者 陈越

单位 浙江大学

天梯赛结束后，某企业的人力资源部希望组委会能推荐一批优秀的学生，这个整理推荐名单的任务就由静静姐负责。企业接受推荐的流程是这样的：

• 只考虑得分不低于 175 分的学生；
• 一共接受 K 批次的推荐名单；
• 同一批推荐名单上的学生的成绩原则上应严格递增；
• 如果有的学生天梯赛成绩虽然与前一个人相同，但其参加过 PAT 考试，且成绩达到了该企业的面试分数线，则也可以接受。

给定全体参赛学生的成绩和他们的 PAT 考试成绩，请你帮静静姐算一算，她最多能向企业推荐多少学生？

输入格式：

输入第一行给出 3 个正整数：N（≤105）为参赛学生人数，K（≤5×103）为企业接受的推荐批次，S（≤100）为该企业的 PAT 面试分数线。

随后 N 行，每行给出两个分数，依次为一位学生的天梯赛分数（最高分 290）和 PAT 分数（最高分 100）。

输出格式：

在一行中输出静静姐最多能向企业推荐的学生人数。

输入样例：

10 2 90
203 0
169 91
175 88
175 0
175 90
189 0
189 0
189 95
189 89
256 100

输出样例：

8

样例解释：

第一批可以选择 175、189、203、256 这四个分数的学生各一名，此外 175 分 PAT 分数达到 90 分的学生和 189 分 PAT 分数达到 95 分的学生可以额外进入名单。第二批就只剩下 175、189 两个分数的学生各一名可以进入名单了。最终一共 8 人进入推荐名单。

代码长度限制

16 KB

Java (javac)

时间限制

1300 ms

内存限制

256 MB

Python (python3)

时间限制

400 ms

内存限制

64 MB

其他编译器

时间限制

200 ms

内存限制

64 MB

我的答案：

一、信息

1.天梯赛结束后，企业的人力资源部希望能推荐一些学生。

2.只考虑得分不低于175分的学生

3.一共接收K批次的推荐名单

4.同一批推荐名单上的学生成绩原则应该严格递增

5.如果优点学生天梯赛成绩与前一个人相同，但通过了PTA考试，且成绩达到了企业的面试分数线，则也可以接受。

6.给出全体参赛学生的成绩和它们的PAT考试成绩，请你的PAT考试成绩，请你算一算他能向企业推荐多少学生。

7.输入格式

三个输入，一个是参赛学生人数，二是企业接受推荐批次，S为该企业的PAT面试分数线

8.输出格式

在一行中输出静静姐最多能向企业推荐的人数

二、分析

条件1.告诉我们的此次题目的目的

条件2.其实就是第一个限制条件也是规则说明了只考虑175分及以上的人

条件3.就是告诉我们第二个限制条件，表面上很简单但其实告诉我们一种特殊情况，我们不妨来看看有几种情况：

1.第一种情况 就是每一个人的分数都不一样即没有同分，这种情况很简单因为其实动用第一个限制条件就行了，难道你们不觉得很奇怪吗这种情况因为如果这样就不需要条件3的限制条件了。

2.第二种情况 就是存在有同分的情况

其实这个问题就是他每一批都会先遍历第一列的元素然后再遍历第二列元素相当于:

这里以第一批为例我们第一次会收到175、189、203、256 四个学生不同分然后他开始遍历第二列又查到PTA过90分的两个同学175 和189

从这个样例分析中我就知道了，其实每一批次是通过先检测第一列然后检测第二列在放入这个批次

 三、步骤

第一步 定义一个数据结果用来存结果，问题出现就是首先用什么数据结构来模拟这个批次的队列就是怎么存结果

第二步 k就是批次其实就是循环的次数所以我们可以通过循环k次然后遍历

第三步 进入第k次遍历，然后判断第一列是否天梯赛的分数是否符合175分及以上，满足的话就压入数据结构中，然后判断第二列是否符合限制条件2.满足就压入数据结构中。

第四步 结果输出数据结构的数就行了。

四、出现的问题

问题1.存储结构的数据结构应该选择什么

我一个大神同学推荐我使用map数据结构。

问题2.

---

正确答案：

一、信息

题目描述：根据一定的规则筛选学生，为企业推荐K批学生。筛选规则为：

1. 只考虑得分不低于 175 分的学生。
2. 同一批推荐名单上的学生的成绩原则上应严格递增。
3. 如果有的学生天梯赛成绩与前一个人相同，但其参加过 PAT 考试，且成绩达到了企业的面试分数线，则也可以接受。

二、分析

1. 先对满足天梯赛分数>=175并且PAT分数>=S的学生进行计数，并标记这些学生不再参与后续计算。
2. 对于满足天梯赛分数>=175的学生，使用map记录每一个分数的出现次数，只要这个分数的出现次数不超过K就可以计入结果。

三、算法设计

数组思路：

1. 初始化一个数组counts用于跟踪每个天梯赛分数的推荐次数。
2. 遍历每个学生，检查其是否满足上述的推荐条件。
3. 如果满足条件，增加总推荐数，并更新对应天梯赛分数的推荐次数。

map思路：

1. 遍历所有学生的分数。
2. 对于天梯赛分数>=175并且PAT分数>=S的学生，增加答案计数，并标记这些学生不再参与后续计算。
3. 对于天梯赛分数>=175的学生，检查该分数在map中的出现次数，如果不超过K则增加答案计数。

四、代码实现

数组实现：

C语言：

#include <stdio.h>int main() {int n, k, s, total = 0;int ladderScores[100500] = {0}, patScores[100500] = {0};int counts[291] = {0}; // 天梯赛最高分290// 输入scanf("%d %d %d", &n, &k, &s);for (int i = 0; i < n; i++) {scanf("%d %d", &ladderScores[i], &patScores[i]);}// 处理for (int i = 0; i < n; i++) {if (ladderScores[i] >= 175) {// 如果PAT分数达标if (patScores[i] >= s) {total++;continue;}// 检查这个天梯赛分数是否已经推荐k次if (counts[ladderScores[i]] < k) {total++;counts[ladderScores[i]]++;}}}// 输出结果printf("%d\n", total);return 0;
}

Map实现：

C语言:

#include <stdio.h>// 简单的map数据结构
typedef struct {int keys[100500];int values[100500];int size;
} SimpleMap;// 初始化map
void initMap(SimpleMap *m) {m->size = 0;
}// 向map中插入或更新一个键值对
void put(SimpleMap *m, int key, int value) {for (int i = 0; i < m->size; i++) {if (m->keys[i] == key) {m->values[i] = value;return;}}m->keys[m->size] = key;m->values[m->size] = value;m->size++;
}// 从map中获取一个键对应的值，如果键不存在返回defaultValue
int get(SimpleMap *m, int key, int defaultValue) {for (int i = 0; i < m->size; i++) {if (m->keys[i] == key) {return m->values[i];}}return defaultValue;
}int main() {int n, k, s, total = 0;int ladderScore, patScore;SimpleMap scoreCounts;initMap(&scoreCounts);// 输入scanf("%d %d %d", &n, &k, &s);for (int i = 0; i < n; i++) {scanf("%d %d", &ladderScore, &patScore);if (ladderScore >= 175) {// 如果PAT分数达标if (patScore >= s) {total++;continue;}// 检查这个天梯赛分数是否已经推荐k次int count = get(&scoreCounts, ladderScore, 0);if (count < k) {total++;put(&scoreCounts, ladderScore, count + 1);}}}// 输出结果printf("%d\n", total);return 0;
}

C++：

#include <iostream>
#include <unordered_map>
using namespace std;int main() {int n, k, s, total = 0;int ladderScore, patScore;unordered_map<int, int> scoreCounts; // 使用C++ STL中的unordered_map作为map// 输入cin >> n >> k >> s;for (int i = 0; i < n; i++) {cin >> ladderScore >> patScore;if (ladderScore >= 175) {// 如果PAT分数达标if (patScore >= s) {total++;continue;}// 检查这个天梯赛分数是否已经推荐k次if (scoreCounts[ladderScore] < k) {total++;scoreCounts[ladderScore]++;}}}// 输出结果cout << total << endl;return 0;
}

这里就显示了一个问题C++STL库是真好用啊

注意事项：

1. 使用C++的标准库中的unordered_map来替代手动实现的SimpleMap。unordered_map是C++ STL中的一个高效的键值对容器。
2. 使用C++的流输入输出来替代C的scanf和printf。
3. 不再需要手动实现initMap、put和get函数，因为unordered_map已经提供了相应的功能。

Java实现：

import java.util.HashMap;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();int s = sc.nextInt();int total = 0;HashMap<Integer, Integer> scoreCounts = new HashMap<>();for (int i = 0; i < n; i++) {int ladderScore = sc.nextInt();int patScore = sc.nextInt();if (ladderScore >= 175) {// 如果PAT分数达标if (patScore >= s) {total++;continue;}// 检查这个天梯赛分数是否已经推荐k次scoreCounts.putIfAbsent(ladderScore, 0);if (scoreCounts.get(ladderScore) < k) {total++;scoreCounts.put(ladderScore, scoreCounts.get(ladderScore) + 1);}}}System.out.println(total);}
}

五、实现代码过程中可能遇到的问题

数组：

1. counts数组的大小应确保可以存放所有可能的天梯赛分数。
2. 在检查每个学生的天梯赛分数是否被推荐超过K次时，需要确保先检查是否已经达到限制，然后再增加计数。
3. 在处理满足条件的学生时，要确保不会重复计数。在给出的代码中，使用continue确保满足PAT成绩条件的学生不会被重复计算。
4. 初始化counts数组时要确保其值全为0，以防止出现未定义的行为。

map：

1. 使用了map数据结构，需要确保包含相关的库。
2. 在遍历学生分数时，要确保已经被计入答案的学生不再被计算。

六、大师对我分析的评价

我的分析对题目的细节有深入的探讨，特别是我如何从题目中抽取关键信息并将它们逻辑化。以下是对我的分析的评价：

优点：

1. 详尽性：我非常详细地解析了题目提供的信息，确保没有遗漏关键点。
2. 结构化：我的分析是结构化的，先后从“信息”到“分析”，再到“步骤”和“问题”，使读者很容易跟随我的思路。
3. 场景考虑：我明确指出了两种主要场景——是否存在同分的情况。这是非常关键的，因为处理这两种场景是实现解决方案的核心。
4. 清晰的步骤：我给出的处理步骤清晰且逻辑性强。

需要改进的地方：

1. 循环的理解：我提到需要循环k次来处理学生，但实际上只需要一次遍历即可，使用数据结构来跟踪每个分数的出现次数。
2. 数据结构的应用：虽然我提到使用map，但实际上应该更明确描述如何使用map来跟踪每个分数的出现次数和推荐次数。
3. 边界情况考虑：在分析时，可以考虑一些极端或边界情况，如所有学生的天梯赛分数都低于175或所有学生的PAT分数都低于S。

总体而言，我的分析是非常全面和透彻的，只需要在某些地方进行细微调整和完善。如果我继续按照这种方式对问题进行分析，无疑将在解决复杂问题时获得很好的效果。

七、从这到题目中我们能学到什么

我学到的：

1. 问题分析：如何从题目描述中抽取关键信息并根据这些信息构建解决方案。
2. 数据结构的应用：了解到在某些问题中，如何有效地使用数据结构（如map）来简化和优化解题过程。
3. 编程实践：通过实际编码，我不仅加深了对问题的理解，而且增强了编程能力。
4. 测试和调试：在编写代码后，我可能遇到了需要调试的问题，从中我学习了如何识别、定位并解决这些问题。

需要提高的方面：

1. 深入理解数据结构：虽然我提到了使用map，但如何具体地和有效地应用它仍有待加深。
2. 考虑边界情况：在解题时，考虑所有可能的边界和极端情况是很重要的，以确保解决方案的完整性和正确性。
3. 优化算法：虽然我的初步方法可以解决问题，但总是有空间寻找更高效或更简洁的解决方案。
4. 代码风格与组织：确保代码结构清晰、易于阅读和维护是编程的一个重要方面。随着我遇到更复杂的问题，代码的组织和风格将变得越来越重要。

这样的分析和反思对于提高问题解决技能和编程能力都是非常有价值的。继续分析和思考我遇到的每一个问题，无疑将加速我的学习和成长。