仓库源文，站点原文

title: "题解 - [Luogu P3878] [TJOI2010] 分金币" categories:

原始题面

现在有 $n$ 枚金币, 它们可能会有不同的价值, 第 $i$ 枚金币的价值为 $v_i$

现在要把它们分成两部分, 要求这两部分金币数目之差不超过 $1$, 问这样分成的两部分金币的价值之差最小是多少?

本题单个测试点内有多组测试数据

输入的第一行是一个正整数 $T$, 表示该测试点内数据组数

对于每组测试数据的格式为:

每组测试数据占两行

第一行是一个整数 $n$, 表示金币的个数

第二行有 $n$ 个整数, 第 $i$ 个整数表示第 $i$ 个金币的价值 $v_i$

对于每组数据输出一行一个整数表示答案

0
2

对 $30\%$ 的数据, 保证 $1 \leq v_i \leq 1000$
对于 $100\%$ 的数据, 保证 $1 \leq T \leq 20$, $1 \leq n \leq 30$, $1 \leq v_i \leq 2^{30}$

看数据范围就知道要折半或者大力模拟退火

模拟退火交了两页, 最高 10 分, 气得我直接码正解去了

今天的爆率那叫一个高啊.webp

令 s[][] 为存所有选取情况的数组, 其中 s[i] 表示前一组金币个数为 $i$ 时的所有可能结果 (或者前一组金币个数比后一组多 $i$ 时个数)

先把前 $\lceil\frac{n}{2}\rceil$ 个金币的所有选取情况存起来, 然后对剩下的 $n-\lceil\frac{n}{2}\rceil$ 个金币的所有情况在对应数组里二分即可

或者我们直接把二维数组换成一维的 std::set 数组也行

$O(n2^\frac{n}{2})$

<details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:Luogu_P3878 Luogu/P3878/0.cpp %} </details>