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)$，主要用于存储每个同学的铅笔数。 ######[AI问答 | 724点数解答 | 2025-12-06 20:58:32]