• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF1416B Make Them Equal

开发技术 开发技术 6小时前 1次浏览

CF1416B Make Them Equal

题意:

一个数列 (a_1 , a_2 … a_n)((a_i geqslant 1))

每次可以选一个三元组 ((x , y , z))(x) 非负 ,(a_i -= x cdot i)(a_j += x cdot i) 。并且操作完之后必须保证所有 (a_i) 非负。

要求用不超过 (3n) 次操作使所有数字均分。

解法:

这题的思路比较好找,因为我们很容易发现 (a_1) 处最灵活,它可以随意的将任意多的 (x) 扔到其它堆里。所以我们用以下的操作:

  1. (a_1)(a_i) 的数字补成 (i) 的倍数,然后再将 (a_i) 的数全部扔到 (a_1) 中。

  2. (a_1) 的数全部均摊到每一个 (a_i) 上。

这个思路非常好理解,操作数最多为 (3(n – 1))

不过为什么能保证它每次操作完后每一项一定非负呢。

操作 2 不用解释了,均摊数值肯定不会出现负数。

而操作 1 最坏的情况就是 (a_i) 全部为 (1) ,这种情况下每次操作都会使被移动的那个结点数值为 (0) 。至于为什么这个情况为最坏情况就不多解释了,显然

时间复杂度:

每组数据 (O(n)) , 总复杂度 (O(t cdot n))

Code


程序员灯塔
转载请注明原文链接:CF1416B Make Them Equal
喜欢 (0)