题解：CF2072A - New World, New Me, New Array

题目分析

题目给出一个长度为 $n$、初始全为 $0$ 的数组。一次操作可以选择一个位置，把它赋值成区间 $[-p,p]$ 中的任意整数。

我们要让数组元素和变成 $k$，并且操作次数尽量少。

关键点有两个：

• 每个被操作过的位置，最终对总和的贡献最多是 $p$，最少是 $-p$。
• 对同一个位置反复赋值没有意义，因为只有最后一次赋值会保留下来，最优方案中每个位置至多操作一次。

暴力为什么已经足够

小数据时可以枚举操作次数 $m$，判断能否用 $m$ 个数，每个数都在 $[-p,p]$ 内，使它们的和为 $k$。

当操作次数固定为 $m$ 时，能得到的和正好覆盖整个区间 $[-mp,mp]$。因此只需要找到最小的 $m$，使得 $|k|\le mp$。

由于题目中 $n\le 50$，直接枚举 $m=0,1,\ldots,n$ 也完全可以通过，复杂度为 $O(n)$。进一步把这个枚举写成公式即可得到更简洁的正解。

正解思路

设 $need=|k|$。

如果所有 $n$ 个位置都使用，数组和的绝对值最大也只能达到 $n\cdot p$。因此：

时无解，输出 $-1$。

否则，每次操作最多让目标和的绝对值增加 $p$。为了用最少的操作凑出绝对值为 $need$ 的和，需要：

次操作。

这个次数一定能构造出来：设 $m=\lceil need/p\rceil$，前 $m-1$ 个被操作的位置可以都赋值为 $p$ 或 $-p$，最后一个位置补足剩余差值即可，剩余差值的绝对值不会超过 $p$。当 $k<0$ 时所有符号反过来即可。

特别地，当 $k=0$ 时，$need=0$，答案为 $0$。

正确性说明

每个位置最终的取值都在 $[-p,p]$ 中，所以操作 $m$ 个不同位置后，总和的绝对值不可能超过 $mp$。因此任何合法方案都至少需要满足 $mp\ge |k|$，也就是操作次数不少于 $\lceil |k|/p\rceil$。

当 $|k|\le n\cdot p$ 时，令 $m=\lceil |k|/p\rceil$，有 $m\le n$。前 $m-1$ 次每次贡献同方向的 $p$，最后一次贡献剩余值，剩余值一定在 $[-p,p]$ 内，所以可以合法完成。于是这个下界可以达到，答案就是 $\lceil |k|/p\rceil$。

复杂度分析

每个测试用例只做常数次计算。

时间复杂度为 $O(1)$，总时间复杂度为 $O(t)$。

空间复杂度为 $O(1)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, k, p;
        cin >> n >> k >> p;

        int need = abs(k);  // 只关心目标和的绝对值，正负对称处理

        // n 个位置全部使用时，最大绝对和也只有 n*p。
        if (need > n * p) {
            cout << -1 << '\n';
        } else {
            // 每次操作最多贡献 p，向上取整得到最少操作次数。
            cout << (need + p - 1) / p << '\n';
        }
    }

    return 0;
}