PKUWC2025 D1T1 详细题解

· · 算法·理论

洛谷没有原题，只能写在算法理论里面……

应同学请求而作。同学找了半天没找到一篇详细的题解，希望这篇题解能够帮助到大家？

这个解法的复杂度仅为 O(t)（即每个测试数据 O(1)）。

题意

题面：有 a+b 个电池，a 个好的，b 个坏的，若当且仅当将两个好的电池匹配时成功，求最坏情况下最小尝试次数。

利用部分分答题

我们发现部分分给出的是 a 和 b 的关系，所以尝试从此处下手。

迈出第一步：a\gt b+1

对于这个微不足道的 5 分：

首先，判断出坏的电池至少得将 b 个电池走一遍，所以判断出所有坏的电池至少需要 b 次。然后，我们随意挑选剩下的两个电池即可：它们一定是好的。那么最少次数应为 b+1。具体参考下图：

好了，现在我们真正踏上了解决此题的旅程！

当 a\le b+1 时呢？

是的，实际上此题只需要分讨两种情况。写的越多越容易错！

此时我们需要知道，到底怎么才能确定一些电池是好的，或是坏的呢？

我们先默认，在确定知道此次必然匹配成功之前，所有操作均为失败。我们需要利用这些失败去确定一些电池是好的或是坏的。

首先，如果我们匹配失败了一次，那么匹配的两个电池中至少一个是坏的。那么，这个东西能不能推广呢？我们能不能推出更多坏的电池呢？

显然可以。我们如果去用 1 个好电池和 x 个坏电池，那么两两配对需要 \frac{(x+1)\times(x+2)}2 次。乍一看好像很浪费呀，但是这已经是压缩的极限，因为如果少了一次，那么那两个没有匹配的电池就可能是双好，对于最坏情况就是 100\%！

所以，我们可以通过 \frac{(x+1)\times(x+2)}2 次尝试去确定在 x+1 个电池中有至少 x 个是坏的。

这让我们思维打开：就算 a 比 b 小，我们依然可以通过操作去完成任务。

对于上面的结论，我们可以用一个函数 \text{solve}(a,b) 来求有 a 个好电池，b 个坏电池时至少需要尝试几次将所有的坏电池确定掉。于是我们使用数学：

我们将 b 分为 x_1+x_2+\ldots+x_a，则总尝试次数为：

\begin{aligned}&\sum_{i=1}^a \frac{(x_i+1)\times(x_i+2)}2&\\=&\ \frac12\sum_{i=1}^a(x_i^2+3x_i+2)&\\=&\ \frac12\sum_{i=1}^ax_i^2+\frac32b+a\end{aligned}

使用调整法：若 \exist\ x_i-x_j>1 则将 x_i 减一，x_j 加一，有

\begin{aligned}&(x_i-1)^2+(x_j+1)^2-x_i^2-x_j^2&\\=&\ x_i^2-2x_i+1+x_j^2+2x_j+1-x_i^2-x_j^2&\\=&\ 2(x_j-x_i+1)&\\\lt&\ 0\end{aligned}

故调整后次数下降，更优；故可将所有 x_i 调整至 \lfloor\frac ba\rfloor 和 \lceil\frac ba\rceil 之间。若令 s=\lfloor\frac ba\rfloor，t=b\mod a 则个数应为 t 个 s+1 和 a-t 个 s。那么，\text{solve}(a,b)=\frac{t\times(s+1)\times(s+2)}2+\frac{(a-t)\times s\times(s+1)}2。可以以下图为例：

至此，我们离正解已经不远了！

我们在筛选出一些坏电池之后，最后只会剩下一些好电池（如果还剩下坏电池，那么后面还要将它们筛选，可以直接与前面 \text{solve} 合体，它们就没有必要出现了）。

于是我们继续分讨：

如果啥都没剩，说明压根选不出来（如果觉得不保险其实也能加，不过实测没有这样的数据。）

如果剩下一个，那么我们需要再找到一个和它配对，我们可以在之前的某个个数最小的组中挑选，参照上面的定义，也就是需要加一个 t+1，从而选出一个好电池。

此状态下答案为 \text{solve}(a-1,b)+(b\mod a)+1

如果剩下超过一个，显然是只需要再配对一次了，所以肯定剩的越少越好，就剩两个即可。

此状态下答案为 \text{solve}(a-2,b)+1

所以，最终答案是两个取最小值，即 \min(\text{solve}(a-1,b)+(b\mod a),\text{solve}(a-2,b))+1。

终于结束了……

代码

很简单，但是作者在场上为了它奋战了两个小时：

#include <bits/stdc++.h>
using namespace std;
int solve(int a, int b) { // 求左 a 右 b 时的最小匹配次数
    if (!a) return 2e9; // 小心除以 0
    int s = b / a, t = b % a;
    return t * (s + 1) * (s + 2) / 2 +
           (a - t) * s * (s + 1) / 2;
}
int main() {
    int _, a, b;
    scanf("%d", &_);
    while (_--) {
        scanf("%d%d", &a, &b);
        if (a > b + 1) printf("%d\n", b + 1);
        else printf("%d\n", min(solve(a - 2, b), solve(a - 1, b) + b / (a - 1)) + 1);
    }
    return 0;
}

制作不易，希望能对大家有所帮助！