CF1416B Make Them Equal
2021/10/15 6:14:56
本文主要是介绍CF1416B Make Them Equal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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\) 扔到其它堆里。所以我们用以下的操作:
-
用 \(a_1\) 将 \(a_i\) 的数字补成 \(i\) 的倍数,然后再将 \(a_i\) 的数全部扔到 \(a_1\) 中。
-
将 \(a_1\) 的数全部均摊到每一个 \(a_i\) 上。
这个思路非常好理解,操作数最多为 \(3(n - 1)\) 。
不过为什么能保证它每次操作完后每一项一定非负呢。
操作 2 不用解释了,均摊数值肯定不会出现负数。
而操作 1 最坏的情况就是 \(a_i\) 全部为 \(1\) ,这种情况下每次操作都会使被移动的那个结点数值为 \(0\) 。至于为什么这个情况为最坏情况就不多解释了,显然。
时间复杂度:
每组数据 \(O(n)\) , 总复杂度 \(O(t \cdot n)\)
Code
这篇关于CF1416B Make Them Equal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享