A. New World, New Me, New Array 详细题解

一、题目理解

初始有一个长度为 $n$ 的全零数组 $a$。每次操作可以选择一个位置 $i$，将其值改为任意整数 $x$，满足 $-p \le x \le p$。目标是通过若干次操作，使数组所有元素之和等于 $k$。求最少操作次数，若不可能则输出 $-1$。

---

二、核心观察

1. 可达和的范围

每次操作可以将某个位置从 $0$ 改为 $[-p, p]$ 内的任意整数。因此：

• 单次操作可以改变数组和的值最多 $\pm p$
• 所有 $n$ 个位置都操作一次后，数组和的取值范围是 $[-n \cdot p, n \cdot p]$

重要结论：数组和可达到的范围是 $[-n \cdot p, n \cdot p]$，且范围内的每个整数都可以达到（因为每次可以调整 $\pm 1$，通过选择合适的 $x$）。

2. 最少操作次数

设最终数组的和为 $k$，初始和为 $0$。

每次操作最多能改变数组和 $p$（正方向）或 $-p$（负方向）。

为了用最少次数达到 $k$，显然应每次尽可能多地向目标靠近：

• 若 $k = 0$：不需要任何操作，答案为 $0$
• 若 $k > 0$：每次操作最多增加 $p$，因此至少需要 $\lceil k/p \rceil$ 次
• 若 $k < 0$：每次操作最多减少 $p$，因此至少需要 $\lceil |k|/p \rceil$ 次

统一公式：

$$\text{最少次数} = \left\lceil \frac{|k|}{p} \right\rceil $$

3. 边界检查

如果 $|k| > n \cdot p$，则即使把所有位置都改成极限值（$\pm p$），也无法达到 $|k|$，此时无解输出 $-1$。

---

三、算法步骤

1. 读入 $n, k, p$
2. 如果 $|k| > n \cdot p$：输出 $-1$
3. 否则，输出 $\lceil |k| / p \rceil$

---

四、公式推导

$$\left\lceil \frac{|k|}{p} \right\rceil = \frac{|k| + p - 1}{p} \quad \text{（整数除法）} $$

标程中的代码：

cout << (abs(k) + p - 1) / p << '\n';

正是这个公式的整数除法实现。

---

五、复杂度分析

• 每个测试用例 $O(1)$
• 总复杂度 $O(t)$，满足 $t \le 1000$

---

六、总结

要点	说明
核心公式	$\lceil
可行范围	$[-n \cdot p, n \cdot p]$ 内所有整数
贪心策略	每次用最大步长 $p$ 向目标靠近
时间复杂度	$O(1)$ 每个测试用例
特殊处理	$k=0$ 时答案为 $0$（公式自动给出）