P1008小核桃与插班生 普及+/提高 CSP-J组 前缀和 差分 标准IO 传统题 来源 TomAnderson 时间限制 1000ms 内存限制 256MB 通过/尝试次数 2903/4997 题目描述 一排学生共 n n 个人在一起听课，分别坐在位置 1 , 2 , 3... n 1,2,3...n，每个人都有一个听课认真度 a i a i ​ ，这时来了一个调皮的插班生，他会影响别人听课。具体来说，距离他 d i s dis 的学生（距离即两个人位置之差的绝对值），听课认真度将减少 n − d i s n−dis，注意，一位学生的听课认真度最低不会低于 0 0。总共有 n n 个座位供插班生选择，被占领座位的学生将被踢出班级，其他人的座位不变，但听课认真度会减少。现在想知道，如果插班生坐在了位置 1 , 2 , 3 , 4... n 1,2,3,4...n，所有学生的听课认真度之和分别是多少。（插班生没有听课认真度） 输入格式 第一行输入一个正整数 n n， 表示学生的个数。 接下来一行输入 n n 个正整数，表示每个学生的听课认真度。 输出格式

以下是使用 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)$，主要用于存储学生的听课认真度。 [2026-02-07 18:26:52 | AI问答 | 642点数解答]