ZJOI2006皇帝的新装

题面传送门

刚看到题,emm这不就是取相邻两个的和的最大值吗,蓝牌题?

不会这么水吧,不管了,先敲敲敲。

果然不出我所料52分。

后来发现一组hack数据,当n=3时,三个数分别是5 5 5,那么我

的算法的答案是10,而正确答案是15;

然后我就想着,问题肯定出在最后一个数,就考虑一下最后一个就行了,但是还是不行,因为最后一个对答案的贡献是受到倒数第二个数影响的。

这样想不行,我们换个思路(虽然有的时候想不到别的思路)

考虑每个颜色,最多给到(n/2下取整)个人。假设我们用x个颜色,那么 x*(n>>1)>=sum;(sum是所有人的所要勋章的总和);

x最小值就是sum/(n>>1),又因为不可能有1.5个颜色,所以我们最后还要向上取整。

然后把两种情况,取个max就是最后的答案了。

因为在第二种情况中,一个颜色有可能无法给到(n>>1)个人,这样可能导致答案不是最大值,所以我们还要考虑第一种情况。

第一种情况下,无论一个颜色贡献给几个人,都会被算上的,所以答案可能变大,也可能变小,所以我们需要第二种情况辅助。

复杂度炒鸡优秀O(n);

code被我吃了


发表于 2018-09-17 22:01:08 in 题目