题目描述】 老师要奖励 N N 名成绩优秀的同学，首先 N N 名同学按随机顺序排成一排，且每名同学都对应一个成绩（成绩各不相同），然后按照如下规则进行奖励。 规则： 每名同学至少奖励 1 1 支铅笔； 每一名同学拿到铅笔后，都会和左右相邻的同学作比较，如果相邻的同学成绩比自己高，那么铅笔数也一定比自己多，如果相邻的同学成绩比自己低，那么铅笔数一定比自己少。（注意每个人成绩都不同） 当给出要奖励的同学数 N N，及 N N 名同学的成绩及排序位置，请你按照规则帮助老师计算出最少需要奖励多少支铅笔。 【输入格式】 第一行输入一个正整数 N N， N N 表示要奖励的同学数。 第二行输入 N N 个正整数，每个正整数表示一名同学的成绩（成绩各不相同），正整数之间以一个英文逗号隔开，正整数的顺序即代表学生的顺序。 【输出格式】 输出一个整数，表示 N N 名同学最少需要奖励的铅笔数。C++

以下是解决该问题的C++代码： ```cpp #include <iostream> #include <vector> #include <sstream> #include <string> using namespace std; // 函数用于将字符串按逗号分割成整数向量 vector<int> split(const string& s) { vector<int> result; stringstream ss(s); string token; while (getline(ss, token, ',')) { result.push_back(stoi(token)); } return result; } int main() { int n; cin >> n; cin.ignore(); // 忽略换行符 string scoresStr; getline(cin, scoresStr); vector<int> scores = split(scoresStr); // 初始化每个同学的铅笔数为1 vector<int> pencils(n, 1); // 从左到右遍历，确保右边成绩高的同学铅笔数更多 for (int i = 1; i < n; ++i) { if (scores[i] > scores[i - 1]) { pencils[i] = pencils[i - 1] + 1; } } // 从右到左遍历，确保左边成绩高的同学铅笔数更多 for (int i = n - 2; i >= 0; --i) { if (scores[i] > scores[i + 1]) { pencils[i] = max(pencils[i], pencils[i + 1] + 1); } } // 计算总共需要的铅笔数 int totalPencils = 0; for (int i = 0; i < n; ++i) { totalPencils += pencils[i]; } cout << totalPencils << endl; return 0; } ``` 代码解释： 1. 输入处理： - 首先读取同学的数量`n`。 - 然后读取一行包含同学成绩的字符串，使用`split`函数将其按逗号分割成整数向量`scores`。 2. 初始化铅笔数： - 创建一个长度为`n`的向量`pencils`，并将每个元素初始化为1，表示每个同学至少有1支铅笔。 3. 从左到右遍历： - 从第二个同学开始，如果当前同学的成绩比前一个同学高，则当前同学的铅笔数为前一个同学的铅笔数加1。 4. 从右到左遍历： - 从倒数第二个同学开始，如果当前同学的成绩比后一个同学高，则当前同学的铅笔数取当前值和后一个同学铅笔数加1的最大值。 5. 计算总铅笔数： - 遍历`pencils`向量，将所有元素相加得到总共需要的铅笔数。 6. 输出结果： - 输出总共需要的铅笔数。 复杂度分析： - 时间复杂度：$O(n)$，其中`n`是同学的数量。需要遍历两次成绩数组。 - 空间复杂度：$O(n)$，主要用于存储每个同学的铅笔数。 [2025-12-06 20:58:32 | AI问答 | 724点数解答]