CF Round 1100 Div12 F - Load Unbalancing

题目大意

原题（CF 2229F） · editorial · jiangly AC

题面

给定长度 $n$ 的序列 $a$ 和整数 $k$ 。可以先任意重排 $a$ 的元素，然后定义 $f(a)$ 如下：

• 令 $b$ 是长度 $k$ 的全零数组。

• 对每个 $1 \le i \le n$ ，把 $a_i$ 加到 $b$ 的任意一个最小元素上。

• 最终 $f(a) = \max(b)$ 。

求所有重排中 $f(a)$ 的最大值。

关键自由度：(1) $a$ 的顺序由我们选；(2) 每步若 $b$ 里多个元素并列最小，加到哪个由我们选。

数据范围

• $1 \le k \le n \le 18$

• $1 \le a_i \le 10^9$

• $\sum 2^n \le 2^{18}$ （所有 testcase 加起来）

• 时限 1.5 s （“unusually low time limit”）

• $t \le 10^4$ testcase

样例

样例 1（ $n=4, k=2, a=[1,2,4,5]$ → 8）：题面给的最优重排是 $[1, 4, 2, 5]$ ， $b$ 演化 $[0,0] \to [1,0] \to [1,4] \to [3,4] \to [8,4]$ ， $\max(b) = 8$ 。

样例 2（ $n=8, k=3, a=[3,4,1,3,2,4,5,3]$ → 11）；样例 3（ $n=3, k=1, a=[10^9,10^9,10^9]$ → $3 \times 10^9$ ）。

---

思路讲解

一句话

$k$ 桶等价， $\max(a)$ 必能放末位（exchange argument），扔掉它后剩下 $n-1$ 个元素装 $k$ 桶最大化 $\min(b')$ ；这是教科书 “max-min partition”，二分答案 + 状压 DP 贪心凑 $\ge k$ 个不相交子集每组 $\mathrm{sum} \ge v$ 。

第 1 步：复杂度预算反推算法

$\sum 2^n \le 2^{18}$ 几乎就是 bitmask DP 的明牌信号。每个 mask 一次 $O(n)$ 转移： $2^{18} \cdot 18 \approx 5 \times 10^6$ ，外层套二分 $\log A$ 系数 $\approx 35$ 倍还在 $10^8$ 以内，1.5 s 紧但能过（“unusually low time limit” 就是预算线索）。

第 2 步：把 $b$ multiset 压成标量——但 simulate 不通

直觉上 dp 状态要追踪当前 $b$ （长度 $k$ 的 multiset），但 $b$ 是 $k$ 维大整数 tuple， $\sum a \le 1.8 \times 10^{10}$ ，装不进 dp 下标。

$\min(b)$ 是"每步加 $a_i$ 的动作锚点"，但单独追踪它不够——加完后新 min 是谁还要看其它桶。死磕 “naive simulate” 路线状压压不下来。

关键扭转：我们不需要 sufficient state 来 simulate。只关心最终的 $\max(b)$ 这一个数，从这个数倒推就豁然开朗。

第 3 步：Observation 1 —— $\max(a)$ 必能放末位

设序列里最后处理的元素是 $a_{\text{last}}$ ，最后一步把它加到某个 min 桶上。最终：

$$\max(b)_{\text{final}} = \max\bigl(\max(b_{\text{before}}),\ \min(b_{\text{before}}) + a_{\text{last}}\bigr)$$

直觉：右项 $a_{\text{last}}$ 越大越占便宜。严格证明用 exchange argument——若最优重排里 $\max(a)$ 不在末位，把它换到末位可证 $\max(b_{\text{final}}) \ge \text{ans}$ 。两 case 分类（ $y$ 原桶仍是 min / $x$ 原桶变成 min）见 editorial 与配套 HTML 演示（下方"动画与源码"节）。

结论：从一开始就锁定 $a_{\text{last}} = \max(a)$ 。

第 4 步：Observation 2 —— 子问题转化为 max-min partition

记 $x = \max(a)$ ， $a' = a \setminus \{x\}$ ， $b'$ = 用 $a'$ 处理完后的 $b$ 状态。

引理： $\max(b') - \min(b') \le \max(a') \le x$ （归纳易得：每步加 $a_i$ 到 min 桶，差要么不增、要么变成 $\le a_i$ ）。

→ $\min(b') + x \ge \max(b')$ 恒成立。所以：

$$\max(b)_{\text{final}} = \max\bigl(\max(b'),\ \min(b') + x\bigr) = \min(b') + x$$

原问题完全等价于：用 $n-1$ 个元素 $a'$ 装 $k$ 桶，最大化最终 $\min(b')$ 。

更进一步（editorial 给的 greedy 构造）：过程约束可以丢。任意一种把 $a'$ 划分成子集的分法 $\{S_j\}$ （每个 $\mathrm{sum}(S_j) \ge v$ ），都能找到合法重排 + tie-breaking 使最终每桶恰好是 $S_j$ （每次从 $S_j$ 里挑剩余最大的元素加）。所以划分本身就是充要条件：

check( $v$ ) = 能否把 $a'$ 划分成 $\ge k$ 个不相交子集，每个 $\mathrm{sum} \ge v$ ？

第 5 步：bitmask DP 的关键 trick —— $k$ 桶等价 + 贪心凑子集

新手一看 check( $v$ ) 容易想成"每个物品 $k$ 种状态"（分到哪个桶），状态空间 $k^n$ 爆。

关键观察：题目里 $k$ 个桶是匿名等价的（不区分 id，只看 multiset）。所以 check( $v$ ) 等价于"贪心一个一个凑子集"——把"凑子集"想成线性流水线：开始 → 凑组 1 → 凑组 2 → … → 凑 $\ge k$ 组 → ✓。

任意时刻状态就两个标量：

• 已封口的合格组数 $\text{cnt}$ —— 已经凑出几个 $\mathrm{sum} \ge v$ 的不相交组。

• 当前未封口组的累加和 $\text{cur}$ —— 还差 $v - \text{cur}$ 就能再封一组（ $\text{cur} < v$ ）。

加上 mask（哪些元素已用）， $dp[\text{mask}] = (\text{cnt}, \text{cur})$ 就够了。

第 6 步：DP 转移

push 风格（jiangly 写法）：

for (int s = 0; s < (1 << n); s++) {
    auto [cur, sum] = dp[s];
    for (int i = 0; i < n; i++) {
        if (~s >> i & 1) {                  // i 不在 s 里
            int t = s | 1 << i;
            int ncur = cur;
            i64 nsum = sum + a[i];          // 把 a[i] 塞进未封口组
            if (nsum >= x) {
                ncur++;
                nsum = 0;                   // 封一个组, leftover 归 0
            }
            dp[t] = std::max(dp[t], std::make_pair(ncur, nsum));
        }
    }
}
return dp.back().first >= k;                // 全集 mask 上至少 k 个组

字典序取 max：先比 cnt 后比 sum 。为什么不只比 cnt？ 同 cnt 下更大 sum 意味着未封口组更接近封口，未来加 1 个元素可能再封一组 → 保留更大 sum 更优（这是经典 max-min partition DP 的字典序套路）。

第 7 步：二分 + 答案

• 二分上界： $\min(b') \le \sum a' / k \le \sum a$ ， $U \approx 2 \times 10^{10}$ ， $\log \approx 35$ 。

• check 一次 $O(2^{n-1} \cdot (n-1))$ 。

• 总： $O(2^{n-1} \cdot (n-1) \cdot \log U)$ ， $n=18$ 时 $\approx 2^{17} \cdot 17 \cdot 35 \approx 7.8 \times 10^7$ 。

• 答案 = $v_{\max} + \max(a)$ 。

退化 case 校验

• $n = 1, k = 1$ ：弹出 $\max$ 后 $a'$ 空，dp 全 0， check 恒 false → $\text{ans} = 0 + a_0 = a_0$ ✓

• $k = 1$ ：全部元素装一桶，答案 = $\sum a$ ✓（check( $\sum a'$ ) 时整个 $a'$ 一组凑成）

• $n = k$ ：每桶恰一元素，答案 = $\max(a)$ ✓

📎 动画与源码

附在末尾「附件」节：

• exchange-argument.html —— 交互式可视化。上半 4 个 preset 数值 demo 看 swap 前后桶演化；下半 Case A / B 抽象代数证明配图（柱高只标 $a, b, c, \text{ans}, \text{ans-y}$ 等代数符号，5 步分步动画）。

• mentor.pdf —— 完整带教对话录（从复杂度预算反推 → Observation 1/2 → bitmask DP 状态设计每一步的引导问题 + me/Claude 气泡留底）。

• 2229F.cpp.txt —— 用户的 AC 实现（push DP，含调试日志宏 + Gosper hack 枚举子集）。

---

AC 代码

AC 提交链接（jiangly 写法参考）

展开完整 C++ 源码（jiangly 风格 push DP）

#include <bits/stdc++.h>
using i64 = long long;
namespace rgs = std::ranges;

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) std::cin >> a[i];
    rgs::sort(a);

    n--;
    int last = a[n];
    a.resize(n);

    auto check = [&](i64 x) {
        std::vector<std::pair<int, i64>> dp(1 << n);
        for (int s = 0; s < (1 << n); s++) {
            auto [cur, sum] = dp[s];
            for (int i = 0; i < n; i++) {
                if (~s >> i & 1) {
                    int t = s | 1 << i;
                    int ncur = cur;
                    i64 nsum = sum + a[i];
                    if (nsum >= x) {
                        ncur++;
                        nsum = 0;
                    }
                    dp[t] = std::max(dp[t], std::make_pair(ncur, nsum));
                }
            }
        }
        return dp.back().first >= k;
    };

    i64 lo = 0, hi = 2E10;
    while (lo < hi) {
        i64 x = (lo + hi + 1) / 2;
        if (check(x)) lo = x;
        else          hi = x - 1;
    }
    std::cout << lo + last << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; std::cin >> t;
    while (t--) solve();
    return 0;
}

---

心路历程

写自己的版本时（pull DP + Gosper hack 枚举固定 popcount 的 sta）一上来踩了两个 bug，自己 debug 出来的：

Bug 1：外层 use 从 1 起，跳过了 use=0 这一层

for (int use = 1; use <= N_1; ++use) {
    long long sta = (1LL << use) - 1;
    while (sta < (1LL << N_1)) {
        // ...
    }
}

use = 当前 source mask sta 的 popcount。从 use=1 起，意思是从 popcount=1 的 mask 出发往外推。唯一显式 init 的只有 dp[0] = {0, 0} 这一格， dp[1] / dp[2] / dp[4] (popcount=1) 这些从未被 dp[0] 推出过，直接拿来当 source 时读到的是 vector default 的 (0,0)——丢了 $A[0]$ 这个元素。

跳 use=0 的真原因：Gosper’s hack 在 sta=0 时 c = sta & -sta = 0 除零崩。正确做法：要么外层 for use = 0 ，要么手动展开 use=0 那一层从 dp[0] 推到所有 dp[1<<i] 。

Bug 2：vis[sta] 跟踪的是 source，但应该跟踪 target

if (vis[sta] == tim) {
    dp[sta | (1ll << i)] = max(now, dp[sta | (1ll << i)]);
} else {
    vis[sta] = tim;
    dp[sta | (1ll << i)] = now;
}

想做"延迟清空 dp"——多次 check 复用 dp 数组，靠 vis[?] == tim 判断"本次 check 是否已 init"。但 vis 应该追踪 target sta | (1<<i) 是否被本次 init 过，写成了 source sta 。后果：

• sta=1, i=1 推 dp[3] ： vis[1] != tim → else， dp[3]=(0,2) 直接覆盖（OK）。

• sta=2, i=0 推 dp[3] ： vis[2] != tim → else， dp[3]=(0,1) 又一次直接覆盖前面的 (0,2) ，没走 max。

每个新 source 第一次进 else 时都会"无条件覆盖"它推出的所有 target——把别的 source 已经 init 过的 dp[target] 丢掉。

正确写法：

int t = sta | (1ll << i);
if (vis[t] == tim) dp[t] = max(now, dp[t]);
else { vis[t] = tim; dp[t] = now; }

验证

两个 bug 都让 check(3) 对样例 1 错返 false，二分塌到 lo=0 ，输出 0 + max(a) = 5 ，期望 8 。修完两条后 sample 全过。

附件

exchange-argument.html 关键帧（Case A 抽象代数证明）

完整 5 步动画（含 Case B 抽象证明）见下方 exchange-argument.html.txt（下载后改回 .html 用浏览器打开 = 可点 Step 看每一帧）。

mentor.pdf — 完整带教对话录

从复杂度预算反推 → Observation 1/2 → bitmask DP 状态设计的全过程引导问答 + me/Claude 气泡留底

源码 & HTML 本体

2229F.cpp.txt

exchange-argument.html.txt