Pascal 代码：实现最优糖果购买方案及复杂度分析

以下是使用 Pascal 语言解决上述问题的代码： ```pascal program CandyPurchase; var n, m, i, j, money, candy_count, max_candy_count: integer; x, y: array[1..100000] of integer; begin // 读取糖果种类数 n 和钱数 m readln(n, m); // 读取每种糖果的价格信息 for i := 1 to n do readln(x[i], y[i]); // 初始化最大糖果数量为 0 max_candy_count := 0; // 遍历所有糖果种类 for i := 1 to n do begin money := m; candy_count := 0; // 模拟购买过程 while money > 0 do begin if (candy_count + 1) mod 2 = 1 then // 购买奇数颗糖果 begin if money >= x[i] then begin money := money - x[i]; candy_count := candy_count + 1; end else break; end else // 购买偶数颗糖果 begin if money >= y[i] then begin money := money - y[i]; candy_count := candy_count + 1; end else break; end; end; // 更新最大糖果数量 if candy_count > max_candy_count then max_candy_count := candy_count; end; // 输出结果 writeln(max_candy_count); end. ``` 代码解释 1. 变量声明： - `n` 表示糖果的种类数，`m` 表示小 R 带的钱数。 - `x` 和 `y` 数组分别存储每种糖果购买第奇数颗和第偶数颗的价格。 - `money` 用于记录每次模拟购买时剩余的钱数，`candy_count` 记录当前购买的糖果数量，`max_candy_count` 记录最大的糖果购买数量。 2. 输入读取： - 首先读取 `n` 和 `m`。 - 然后通过循环读取每种糖果的价格信息，存储到 `x` 和 `y` 数组中。 3. 模拟购买过程： - 对于每种糖果，初始化 `money` 为 `m`，`candy_count` 为 0。 - 在 `while` 循环中，根据当前要购买的是奇数颗还是偶数颗糖果，检查 `money` 是否足够支付相应价格。如果足够，扣除相应的钱数并增加 `candy_count`；如果不够，则跳出循环。 4. 更新最大糖果数量： - 每次完成一种糖果的购买模拟后，比较 `candy_count` 和 `max_candy_count`，如果 `candy_count` 更大，则更新 `max_candy_count`。 5. 输出结果： - 最后输出 `max_candy_count`。 复杂度分析 - 时间复杂度：$O(n * \frac{m}{\min(x_i, y_i)})$，其中 $n$ 是糖果的种类数，$m$ 是小 R 拥有的钱数，$\min(x_i, y_i)$ 是每种糖果价格中的较小值。对于每种糖果，最多需要进行 $\frac{m}{\min(x_i, y_i)}$ 次购买尝试。 - 空间复杂度：$O(n)$，主要用于存储每种糖果的价格信息。 ######[AI问答 | 822点数解答 | 2025-12-11 11:53:17]