首页 > 石子搬运
开通博客写题解
头像 白菜茄子
发表于 2020-03-16 16:30:06
网址：https://ac.nowcoder.com/acm/contest/4743/E 题目描述 有{n堆石子，第i堆石子的石子数量是ai，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是k，那么这堆石子将对牛牛产生k^2的负担值。牛牛最多只能搬运m次，每次搬运可 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-03-10 14:51:33
Solution 首先我们思考一个简化版的问题，如果不支持修改，我们如何找到搬运完全部石头数的最优解。考虑动态规划解题，对于一堆石子来说，我们可以枚举搬运次数，根据求解的消耗是很容易发现数学规律，我们要让每次搬运的石头尽可能相同的多，就算有不同的不同的两次之间绝对值差值只能小于等于。那么我们考虑代表 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 jzdx（hjh）
发表于 2021-03-12 10:29:28
题号 NC200214名称 石子搬运来源 牛客练习赛59 题目描述 有n堆石子，第i堆石子的石子数量是ai，作为牛客网的一头领头牛，牛牛决定把这些石子搬回牛客。如果牛牛一次搬运的石子数量是k，那么这堆石子将对牛牛产生k^2的负担值。牛牛最多只能搬运m次，每次搬运可以从一堆石子中选出一些石子搬回牛客， 展开全文
去ta的博客 赞 (0) 回复(1) 收起
头像 shyyhs
发表于 2021-03-11 14:23:34
思路 我线段树属于那种看到题解一般能懂,自己有时候想不到的层次...这题应该就是一个线段树...单纯的已知次数下搬运石头肯定是平方答案最优.然后假如不含修改的话,就是一个超级简单的.假如含有修改呢...我们不妨把它放到线段树上进行.令表示为到了这个石头堆(因为线段树是一群一群石头进行维护的嘛~)选了 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Eihuvita.
发表于 2021-03-11 20:57:03
题意 有堆石头 牛牛每次都能选择其中一堆然后将其中的石头搬走 如果一次搬运的石子数量是那么这堆石头讲牛牛产生的的负担 然后牛牛最多只能搬次 然后牛能会进行次操作 每一次操作都会改变一堆石子的数量 然后让我们求牛能每一次操作之后 牛牛的最小负担 首先我们不看牛能的操作 很明显对于求牛牛的负担就是一个的 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”