一道神仙题
神仙神仙题。
非常的NB,首先,考虑答案的上界。
上界
考虑大概就是这么一个情况,我们不希望过多的“小”的最后剩下了,使得出现不得不放置>=3个的。
而小的和小的很可能达不到
由于平均数的特性,大的加小的一定在平均数之上,我们删去最小的,和最大的部分,转化为子问题。
所以不难发现我们构造出来上界
值得注意的:这个构造的确不是最优的,我们武断的删除最大值部分可能不是最优的,但是合法的,这足够了。
我们默认了A也就是答案的值,我们现在本质上在判断每一个A是否合法。
我们使用语言描述一下我们的 observation。
当我们有
现在我们可以暴力枚举答案了,那么接下来该怎么判断每一个A是否合法呢?
考虑实际上,我们选出一个饮料的子集,
此时我们需要证明的是,任意的选饮料的情况能被上述方法表示出了。
根据题解的证明,我们将一种饮料在两个杯子里看作一种“分裂”,那么我们把“分裂”的两个结点(两个杯子)连边,会形成若干个连通块。
我们需要说明,将这些连通块再次分组,可以使得每一个组内,饮料集合
首先点数为
有点乱是吧
题解写的非常乱套,所以我一步一步说:
“首先你看如果这个连通块是树,那么
我们可以认为最初有
这个自然合法。
我们希望每一个组内饮料数-瓶子数=1.
等一下????
如果一个图想联通,必须满足
这个用语言描述就是如果现在有
考虑我们应让
所以得证,我不确定。
做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?做法呐?
呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐呐?
注意限制!!当A固定的时候,找到的一组应该满足
AC了woc,绝世好题。。。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!
v1.4.14