一道神仙题

神仙神仙题。

LINK

非常的NB，首先，考虑答案的上界。

上界

考虑大概就是这么一个情况，我们不希望过多的“小”的最后剩下了，使得出现不得不放置>=3个的。

而小的和小的很可能达不到 \(\mathrm{sum}/A\) ，所以考虑我们可以取出最大的和最小的。

由于平均数的特性，大的加小的一定在平均数之上，我们删去最小的，和最大的部分，转化为子问题。

所以不难发现我们构造出来上界 \(n-1\)。

值得注意的：这个构造的确不是最优的，我们武断的删除最大值部分可能不是最优的，但是合法的，这足够了。

我们默认了A也就是答案的值，我们现在本质上在判断每一个A是否合法。

我们使用语言描述一下我们的 observation。

当我们有 \(x\) 瓶饮料时，我们能构造出来一种只需要 \(x-1\) 个瓶子的方案。满足 \(\sum_{x \in S}x=(|S|-1)\frac{sum}{A}\)。

---

现在我们可以暴力枚举答案了，那么接下来该怎么判断每一个A是否合法呢？

考虑实际上，我们选出一个饮料的子集,\(S\),使得 \(\sum_{x\in S}x=(|S|-1)\frac{sum}{A}\) ，这个的涵义与上述构造方案相同。

此时我们需要证明的是，任意的选饮料的情况能被上述方法表示出了。

根据题解的证明，我们将一种饮料在两个杯子里看作一种“分裂”，那么我们把“分裂”的两个结点(两个杯子)连边，会形成若干个连通块。

我们需要说明，将这些连通块再次分组，可以使得每一个组内，饮料集合 \(S\)，满足 \(\sum_{x\in S}x=|S-1|\frac{sum}{A}\)。 （只要能分出来一定就是 \(N-A\) 个组（（（（ N是饮料个数，A是瓶子个数

首先点数为 \(|V|=A\),边数 \(|E|\leq 2A-N\)。

---

有点乱是吧

题解写的非常乱套，所以我一步一步说：

“首先你看如果这个连通块是树，那么 \(n\) 个点 \(n-1\) 条边（合并）”

我们可以认为最初有 \(2n\) 种饮料(每个瓶子里放两种)，然后一次合并减少一种，所以现在这个共有 \(2n-(n-1)=n+1\) 种饮料。

这个自然合法。

我们希望每一个组内饮料数-瓶子数=1.

---

等一下？？？？

如果一个图想联通，必须满足 \(|E|\geq |V|-1\),饮料数 \(\text{drinks}=2|V|-|E|\leq|V|+1\)

这个用语言描述就是如果现在有 \(B_i=|V|\) 个相关的瓶子（联通），那么饮料数不应该超过 \(D_i=|V|+1\)。

考虑我们应让 \(\sum_{i=1}B_i=A,\sum_{i=1}D_i=N\)。

\(B_i-D_i\ge -1\)。

\(\sum B_i-D_i=A-D<0\)，这个表明如果我们有一个 \(B_i-D_i\ge0\) 那么我们始终有 \(-1\) 让他变小。

所以得证，我不确定。

---

做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？做法呐？

呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐？

注意限制！！当A固定的时候，找到的一组应该满足 \(\sum_{x\in S}x=(|S|-1)\frac{sum}{A}\)，后面的看作常量，那就是每一个数减去 \(\frac{sum}{A}\)，然后就是每一组应该满足 \(\sum_{x\in S}x=-\frac{sum}{A}\)。我们限制就任意选一组 \(\{x_i\}\)即可，考虑如果有交，那么互相交换即可。好有道理的样子呢！

AC了woc,绝世好题。。。