CCF CSP 2017.09：分组计算与公共钥匙盒问题解码

在CCF CSP 2017.09的编程竞赛中，两道题目分别是“CCF201709-1 打酱油”和“CCF201709-2 公共钥匙盒”，均为满分100分的C++代码实现。 CCF201709-1 打酱油 这是一道关于货币兑换的问题。题目要求以5瓶一组购买，余下部分以3瓶一组购买，最后剩余的按10元/瓶计算。解题的关键在于理解分组策略并应用到程序中。程序中定义了常量，如1瓶的价格、5瓶的价格、3瓶的价格以及10元的价格，这样可以提高代码的可读性和复用性。通过输入的瓶子数量n，计算出分别按照5瓶、3瓶和单独购买的组合数，最后将这些组合相加得到最终结果。 ```cpp int main(void) { int n, group1, group2, group3; scanf("%d", &n); group1 = n / (PRICE * FIVE); // 5瓶一组的数量 group2 = (n - group1 * PRICE * FIVE) / (PRICE * THREE); // 3瓶一组的数量 group3 = (n - group1 * PRICE * FIVE - group2 * PRICE * THREE) / PRICE; // 单独购买的数量 printf("%d\n", group1 * (FIVE + TWO) + group2 * (THREE + ONE) + group3); // 结果输出 return 0; } ``` CCF201709-2 公共钥匙盒 这是一道模拟现实场景的问题，涉及到优先队列（如二叉堆）的应用。主要任务是跟踪N个教室的钥匙在公共钥匙盒中的动态变化。每个老师上课和下课的过程都需要操作钥匙，包括取钥匙（找寻并拿走需要的钥匙）、还钥匙（挂到最左边的空挂钩上，并确保按钥匙编号从小到大排序）。题目要求在给定的时间线和操作顺序下，预测钥匙盒内钥匙的最终排列。 为了解决这个问题，程序需要设计一个数据结构来模拟钥匙盒的状态，同时处理取钥匙和还钥匙的操作。可能的做法是使用优先队列（最小堆），这样每次还钥匙时，都能快速找到下一个空位。当有多位老师操作时，程序需确保按照一定的规则（如按编号或时间）进行同步。 ```cpp // 代码省略了具体实现，但可能包含以下部分 struct KeyInfo { int key, startTime, endTime; }; std::priority_queue<KeyInfo> keyBox; // 使用优先队列存储钥匙信息 void takeKey(int key, int teacherId) { // ... 操作优先队列取钥匙 ... } void returnKey(int key) { // ... 操作优先队列还钥匙，保持按编号或时间排序 ... } int main() { int N, K; scanf("%d%d", &N, &K); for (int i = 0; i < K; ++i) { int w, s, c; scanf("%d%d%d", &w, &s, &c); // 读取老师的信息 KeyInfo info = {w, s, s+c}; // 计算下课时间 // ... 处理取钥匙和还钥匙操作 ... } // ... 最终打印钥匙盒的顺序 ... return 0; } ``` 这两道题目考察了参赛者对基础数据结构（数组、常量定义、优先队列）的理解和实际编程能力，同时也体现了算法设计在解决实际问题中的应用。