在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;
}
```
这两道题目考察了参赛者对基础数据结构(数组、常量定义、优先队列)的理解和实际编程能力,同时也体现了算法设计在解决实际问题中的应用。