CSP - J组难题破解：插班生入座对学生听课认真度总和的影响及C++实现

以下是使用 C++ 解决该问题的代码： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; // 存储每个学生的听课认真度 vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } // 遍历插班生可能坐的每个位置 for (int seat = 1; seat <= n; ++seat) { int totalAttention = 0; // 重新复制一份听课认真度数组，避免修改原始数组 vector<int> attention = a; // 被占领座位的学生听课认真度变为 0 attention[seat] = 0; // 计算每个学生听课认真度的减少量 for (int i = 1; i <= n; ++i) { if (i != seat) { int dis = abs(i - seat); int decrease = n - dis; // 确保听课认真度不低于 0 attention[i] = max(0, attention[i] - decrease); } } // 计算所有学生的听课认真度之和 for (int i = 1; i <= n; ++i) { totalAttention += attention[i]; } // 输出结果 cout << totalAttention; if (seat < n) { cout << " "; } } cout << endl; return 0; } ``` 代码解释： 1. 输入处理：首先读取学生的数量 `n`，然后读取每个学生的听课认真度，存储在数组 `a` 中。 2. 遍历插班生可能的座位：使用 `for` 循环遍历插班生可以坐的每个位置。 3. 模拟插班生入座：对于每个座位，复制一份听课认真度数组 `attention`，将被占领座位的学生听课认真度设为 0。 4. 计算听课认真度的减少量：遍历每个学生，计算其与插班生的距离 `dis`，进而得到减少量 `n - dis`，同时确保每个学生的听课认真度不低于 0。 5. 计算总听课认真度：将所有学生的听课认真度相加，得到总听课认真度。 6. 输出结果：输出每个插班生座位对应的总听课认真度，用空格分隔。 复杂度分析： - 时间复杂度：$O(n^2)$，因为对于每个插班生座位，都需要遍历一次所有学生。 - 空间复杂度：$O(n)$，主要用于存储学生的听课认真度。 ######[AI问答 | 642点数解答 | 2026-02-07 18:26:52]