CCF CSP 2017.03 题解：分蛋糕与学生排队的C++代码实现

"CCF CSP 2017.03 第10次题目答案代码.docx" 本文将详细讨论两个CCF CSP（中国计算机学会软件能力认证）2017年第三次考试的编程题目，包括“分蛋糕”和“学生排队”的解决方案，以及对应的C++代码实现。 首先，我们来看“分蛋糕”（CCF201703-1）的问题。这是一个数据分组问题，要求将一系列整数分组，使得每组的和大于或等于给定的阈值k，但允许最后一组的和小于k。解决这个问题的关键在于跟踪当前组的累计和（sub）以及组的数量（count）。程序中，通过一个循环遍历输入的所有整数，将每个数累加到sub上，当sub大于等于k时，增加计数count并重置sub为0。如果在遍历结束后sub仍然大于0，表示还剩下一些未分组的数值，因此count需要再加1。最后输出count即为满足条件的组数。 接下来，我们讨论“学生排队”（CCF201703-2）的解题思路。这是一个模拟题，主要考察数据结构的选择和操作效率。题目要求根据一系列操作更新学生在队列中的位置。这里有四种不同的解决方案： 1. 使用两个数组sno2pos[]和pos2sno[]，前者记录学生编号到位置的映射，后者记录位置到学生编号的映射。这种方法执行速度快，但需要额外的空间。 2. 仅使用一个数组pos2sno[]记录位置到学生编号的映射，查找学生位置时需要顺序搜索，虽然逻辑简单，但效率较低。 3. 使用STL的list（链表）实现，链表便于插入和删除操作，但查找效率低。 4. 使用STL的vector实现，代码简洁，通过下标访问元素，但插入和删除操作可能不如链表高效。 在实际编程竞赛中，根据时间和空间复杂度的考量，方法二（仅用pos2sno[]数组）可能是最好的选择，因为它在得分方面表现优秀，而方法一（双数组）则在时间和空间效率上有优势。 以下是使用STL的vector实现的学生排队问题的C++代码片段： ```cpp /*CCF201703-2学生排队*/ #include<iostream> #include<vector> using namespace std; vector<int> v; int find(int x) { int ret = -1; for (int i = 0; i < (int)v.size(); i++) if (v[i] == x) return i; return ret; } int main() { int n, m, p, q; // ... 输入和操作处理 ... } ``` 在这个解决方案中，`find`函数用于查找学生在队列中的位置，通过遍历vector v来实现。这种方法虽然简洁，但在频繁的插入和删除操作中可能不如链表高效。 总结来说，这两个CCF CSP题目考察了数据分组和队列操作的算法设计与实现。对于分蛋糕问题，关键在于正确地累计和检查是否满足分组条件；对于学生排队问题，选择合适的数据结构和操作方式至关重要。在实际编程中，需要权衡代码的简洁性、运行效率和内存占用。