U525664 「KTSC 2022 R2」寻找魔法珠 剩余数据测试处
题目背景
**请使用 C++17 或 C++20 提交本题**
你需要在程序开头加入如下代码:
```cpp
#include
int count(std::vector P);
```
题目译自 [2022년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2022/) T2「 [마법 구슬 찾기](https://assets.ioikorea.kr/ioitst/2022/2/marbles/marbles_statement.pdf)」
题目描述
你有 $k+1$ 颗外观和质量完全相同的珠子,其中 $k$ 颗是普通珠子,$1$ 颗是魔法珠子。你需要找到这颗魔法珠子,才能进入魔法城堡。
虽然无法通过肉眼区分魔法珠子和普通珠子,但你可以使用 $M (M \geq 2)$ 个袋子来找到魔法珠子。袋子编号从 $0$ 到 $M-1$。
找到魔法珠子的步骤如下:
1. 将所有珠子分装到 $M$ 个袋子中。
- 每个袋子里必须有珠子,不能有空袋子。
- 袋子里只能装珠子,不能装其他袋子。
2. 念咒语。
3. 念咒语后:
- 不含魔法珠子的袋子里的珠子会全部消失。
- 含有魔法珠子的袋子里的珠子会因为魔法珠子的保护而不消失,但需要支付费用。若魔法珠子在第 $i$ 个袋子中,且该袋子里有 $j$ 颗珠子,则费用为 $A[i] \times j + B[i] (A[i] \geq 0, B[i] \geq 1)$ 元。
魔法珠子永远不会消失,因此你可以重复上述步骤,直到只剩下魔法珠子。
你需要制定一个策略,将珠子分装到袋子中,以最小化在最坏情况下找到魔法珠子的费用。也就是说,无论哪颗珠子是魔法珠子,总费用不超过 $w$ 元,找出最小的 $w$。
请编写一个函数,解决 $0$ 到 $N-1$ 的所有 $k$ 的问题。
你需要实现以下函数:
`vector find_minimum_costs(int N, vector A, vector B);`
- `N`:珠子的最大数量
- `A, B`:长度为 $M$ 的数组。对于每个 $i (0 \leq i \leq M-1)$,若魔法珠子在第 $i$ 个袋子中,且该袋子里有 $j$ 颗珠子,则费用为 $A[i] \times j + B[i]$ 元。
- 该函数返回一个长度为 $N$ 的数组 $C$。对于每个 $k (0 \leq k \leq N-1)$,$C[k]$ 是在有 $k$ 颗普通珠子和 $1$ 颗魔法珠子的情况下,找到魔法珠子的最坏情况下的最小费用(单位:元)。
注意,提交的代码中不应包含任何输入输出操作。
输入格式
无
输出格式
无
说明/提示
### 样例解释 #1
考虑 $N=3, M=2, A=[1,3], B=[2,1]$ 的情况。
评测程序将调用如下函数:
`find_minimum_costs(3, {1,3}, {2,1});`
当 $k=0$ 时,只有一颗珠子,即魔法珠子,因此费用为 $0$ 元。
当 $k=1$ 时,可以将两颗珠子分别放入两个袋子。若魔法珠子在第 $0$ 个袋子中,费用为 $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$ 元;若魔法珠子在第 $1$ 个袋子中,费用为 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元。因此,最坏情况下费用为 $4$ 元。
当 $k=2$ 时,可以采用以下策略。假设三颗珠子分别为 $X, Y, Z$。
- 将 $X$ 和 $Z$ 放入第 $0$ 个袋子,将 $Y$ 放入第 $1$ 个袋子,然后念咒语。
- 若魔法珠子在第 $0$ 个袋子中,费用为 $A[0] \times 2 + B[0] = 1 \times 2 + 2 = 4$ 元,剩下 $X$ 和 $Z$。然后将 $Z$ 放入第 $0$ 个袋子,将 $X$ 放入第 $1$ 个袋子,再次念咒语。
- 若魔法珠子在第 $0$ 个袋子中,费用为 $A[0] \times 1 + B[0] = 1 \times 1 + 2 = 3$ 元,剩下 $Z$。
- 若魔法珠子在第 $1$ 个袋子中,费用为 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元,剩下 $X$。
- 若魔法珠子在第 $1$ 个袋子中,费用为 $A[1] \times 1 + B[1] = 3 \times 1 + 1 = 4$ 元,剩下 $Y$。
在这种策略下,若 $X$ 是魔法珠子,总费用为 $4 + 4 = 8$ 元;若 $Y$ 是魔法珠子,总费用为 $4$ 元;若 $Z$ 是魔法珠子,总费用为 $4 + 3 = 7$ 元。因此,最坏情况下费用为 $8$ 元。
函数应返回 `[0,4,8]`。