QOJ 14706 - A Lot of Paintings 题解：差值分摊与四舍五入边界分析

一、 题目大意

画展共有 $n$ 个人参加，每个人提交了 $b_i$ 幅画，画作总数为 $m = \sum_{i=1}^n b_i$。
现在总数 $m$ 和具体的 $b_i$ 都丢失了，只记录了每个人占总数的百分比四舍五入到整数后的结果 $d_1%, d_2%, \dots, d_n%$（例如占比 $24.5%$ 会被记录为 $25$）。

请根据这 $n$ 个整数百分比，还原出一组可能的画作数量 $b_1, b_2, \dots, b_n$（要求 $0 \le b_i \le 10^9$ 且总和大于 $0$）。如果无论如何都凑不出合法的画作数量，输出 No。

二、 核心解题思路：差值分摊与左右边界

如果去枚举或搜索“真实的画作总数 $m$”，复杂度极高。最清晰的思路是从“输入总和与 $100%$ 的偏差”切入：

1. 为什么要算和 100 的差值？

真实的百分比之和必定严格等于 $100%$。但由于每个数都被四舍五入过，输入的这 $n$ 个百分比相加（记为 sum_d），往往不等于 $100$：

  • 如果 sum_d >= 100：说明四舍五入时进位偏多，还原真实值需要大家向下削减，需要削减的总量为 diff = sum_d - 100。
  • 如果 sum_d < 100：说明四舍五入时舍去偏多，还原真实值需要大家向上补充，需要补充的总量为 diff = 100 - sum_d。

将 diff 统一定义为需要调整的正数绝对差值，不仅正负号直观清晰，更便于后续统一步调分摊。

问题的核心随之转化为：把 diff 分摊到每个人身上去承担，检查这 $n$ 个人能否在不改变四舍五入结果的前提下，消化完这个差值。

2. 每个数最多能承担多少？（核心不等式）

根据四舍五入规则（满 $0.5$ 进位，不满 $0.5$ 舍去），每个数大约能承担 $0.5%$ 的变动，但左边界与右边界具有不对称性（一个带等号，一个不带等号）：

  • 情况一：向下削减（左边界，带等号）
    若某人的记录值为 $25%$，其真实值最小可以达到 $24.5%$，因为 $24.5%$ 小数位正好是 $.5$，按规则依然向上进位成 $25%$。
    即：    每个数最多可以向下减 $0.5%$（可取等号）    。如果所有人能提供的最大削减总量达到 diff，即有解：

$$0.5 \times n \ge \text{diff}$$

  • 情况二：向上补充（右边界，不带等号）
    若某人的记录值为 $25%$，其真实值绝不能达到 $25.5%$（否则就会进位为 $26%$），它最大只能无限接近但小于 $25.5%$（即 $25.49\dot{9}%$）。
    即：    每个数向上增加的幅度必须严格小于 $0.5%$（不可取等号）    。因此 $n$ 个数能提供的最大增加总量必须严格大于 diff：

$$0.5 \times n > \text{diff}$$

三、 从思路到工程落地的三个细节

明确了不等式后，编写代码时需要注意以下三个工程细节：

细节 1：元素为 0 的边界限制（谁能承担差值？）

题目要求还原的画作数量非负（$b_i \ge 0$），使得 0 在两种情况下的性质截然不同：

  1. 向下削减时，0 不能参与：
    如果某人的比例原本就是 $0%$，再削减就会产生负数画作数量，这是非法的。因此只有初始值大于 0 的元素才能提供削减空间。代码中使用 non_zero_cnt 统计大于 0 的人数，合法判定为：

$$\text{non_zero_cnt} \times 0.5% \ge \text{diff}$$

  1. 向上补充时，0 完全可以参与：
    若某人原本为 $0%$，将其微调至 $0.499\dots%$，四舍五入后依然是 $0%$，且数量为正，完全合法。因此所有 $n$ 个元素均可参与分摊，合法判定依然为：

$$n \times 0.5% > \text{diff}$$

细节 2：精度放大与常数定义（避免精度丢失）

输出结果必须是整数。如果仅将所有数放大 10 倍（固定总数为 1000），向上微调的最大整数只能取 +4（对应 $+0.4%$），相当于白白丢掉了接近 $0.1%$ 的上调空间；当 $n$ 较大时，累积的误差会导致本该有解的用例被误判为 No。

为了彻底消除误差，直接利用题目给出的上限 $b_i \le 10^9$，将输入放大 $10^7$ 倍（相当于将画作总数固定为 $m = 100 \times 10^7 = 10^9$）：

  • 整体缩放倍数：SCALE = 10000000（即 $10^7$）；
  • 单个数最大下调量：MAX_DEC = 5000000（对应 $0.5%$）；
  • 单个数最大上调量：MAX_INC = 4999999（对应 $0.4999999%$）。

还要注意，sum_d 和 diff 都以整数个百分点计。判定式左侧 $0.5 \times n$ 以半个百分点为步长；当 $0.5 \times n > \text{diff}$ 成立时，二者的差至少为 $0.5%$，也就是 5000000 个缩放单位。每个元素因严格小于边界而损失 1 个单位；题目保证 $\sum n \le 2 \times 10^5$，所以总损失最多为 200000 个单位，小于这部分余量，贪心分摊仍能完成。

细节 3：贪心分摊逻辑

在判定为 Yes 后，使用变量 rem（Remaining）记录待分摊的差值。遍历数组进行贪心填充（优先填满当前元素，不够填满则全部消耗）：

  • 向下削减： 遇到 b[i] > 0 的位置，减去 delta = min(rem, MAX_DEC)，同步更新 rem -= delta，直到 rem == 0。
  • 向上补充： 对任意位置均可加上 delta = min(rem, MAX_INC)，同步更新 rem -= delta，直到 rem == 0。

四、 标准 AC 代码

代码去除了易混淆的缩写，定义了清晰的常量，并将差值与剩余量统一为正数进行逻辑处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// 定义常量：固定总和为 10^9，对应 1% 放大为 10^7
const LL SCALE = 10000000LL;   // 缩放基数
const LL MAX_DEC = 5000000LL;  // 单个元素最大下调容量 (0.5%)
const LL MAX_INC = 4999999LL;  // 单个元素最大上调容量 (0.4999999%)

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    LL T;
    cin >> T;

    while (T--) {
        LL n;
        cin >> n;

        vector<LL> b(n);
        LL sum_d = 0;
        LL non_zero_cnt = 0; // 统计非零元素个数（仅非零元素可向下削减）

        for (LL i = 0; i < n; i++) {
            LL d;
            cin >> d;
            b[i] = d * SCALE;
            sum_d += d;
            if (d > 0) non_zero_cnt++;
        }

        // 情况 1：总和偏大或刚好等于 100，需要向下削减
        if (sum_d >= 100) {
            LL diff = (sum_d - 100) * SCALE; // 需要削减的正差值

            if (non_zero_cnt * MAX_DEC >= diff) {
                cout << "Yes\n";

                LL rem = diff; // 剩余待削减量
                for (LL i = 0; i < n && rem > 0; i++) {
                    if (b[i] > 0) {
                        LL delta = min(rem, MAX_DEC);
                        b[i] -= delta;
                        rem -= delta;
                    }
                }

                for (LL i = 0; i < n; i++) {
                    cout << b[i] << (i == n - 1 ? '\n' : ' ');
                }
            } else {
                cout << "No\n";
            }
        }
        // 情况 2：总和偏小，需要向上补充
        else {
            LL diff = (100 - sum_d) * SCALE; // 需要补充的正差值

            // 核心不等式：0.5% * n > diff
            if (n * MAX_DEC > diff) {
                cout << "Yes\n";

                LL rem = diff; // 剩余待补充量
                for (LL i = 0; i < n && rem > 0; i++) {
                    LL delta = min(rem, MAX_INC);
                    b[i] += delta;
                    rem -= delta;
                }

                for (LL i = 0; i < n; i++) {
                    cout << b[i] << (i == n - 1 ? '\n' : ' ');
                }
            } else {
                cout << "No\n";
            }
        }
    }

    return 0;
}

五、 复杂度分析

  • 时间复杂度： 读入数据、贪心分摊、输出结果均只需单重线性循环，单个测试用例时间复杂度为 $\mathcal{O}(n)$，总时间复杂度为 $\mathcal{O}(\sum n)$。题目保证 $\sum n \le 2 \times 10^5$，因此总处理量为线性级别。
  • 空间复杂度： 仅使用长度为 $n$ 的 vector<LL> b 存储调整后的结果数组，空间复杂度为 $\mathcal{O}(n)$。