首页 > 试题广场 >

取球放球

[编程题]取球放球
  • 热度指数：845 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有n个箱子，第i个箱子一开始有a_i个球，你可以进行最多k次操作，每次操作可以从一个箱子拿走一个球或者放入一个球。第i个箱子最多能装w_i个球，装满了之后不能再往这个箱子里面放球。如果一个箱子为空，就不能从里面拿球。
设相邻箱子的球的数量的差的平方中的最大值为x，求进行最多k次操作之后x最小可以是多少。


示例1

输入

5,4,[12,4,7,9,1],[15,15,15,15,15]

输出

36

说明

往第2个箱子放2个球，往第4个箱子放2个球得到[12,6,7,9,3],此时相邻箱子的球数差值为[-6,1,2,-6],平方后为[36,1,4,36]，其中最大值为36

备注:
，
算法知识视频讲解
开通博客
头像 积极的防守者
发表于 2020-02-06 21:43:50
普通解法 考虑动态规划 用表示考虑前个数字,操作次，最后一个数字是的情况下相邻项的差的平方的最大值的最小值. 有了这个定义之后，转移就比较显然了： 可以转移其中和取决于对位置的操作。 int solve(int n, int k, vector<int> a, vector<int 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Maokt
发表于 2021-08-08 00:13:58
算法思想一：贪心 解题思路： 利用贪心思想，利用一个辅助数组每次操作前记录相邻两个数组之差，并找到差的最大值的下标。这种时候我们有两种选择：较大的那个数减少，或者较小的那个数增大，每次操作时需要盘旋小数和大数谁在前，需要判断边界，需要判断前后一个数更改谁使最大值最小。 dp记录相邻 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客534170409号
发表于 2021-08-05 00:34:41
题目描述 有个箱子，第个箱子一开始有个球，进行最多次操作，每次操作可以从一个箱子拿走一个球或者放入一个球。第个箱子最多能装个球。如果一个箱子为空，就不能从里面拿球。设相邻箱子的球的数量的差的平方中的最大值为，求进行最多次操作之后最小可以是多少。 方法一 贪心+模拟 解题思路 一个比较直接的思路是 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-02 13:02:42
思路： 题目的主要信息： 一共n个箱子，每个箱子有一定容量和一定初始球个数 进行k次操作，每次操作对某一个箱子中的球进行加1或者减1 求k次操作之后要使任意相邻箱子球数差的平方的最大值达到最小。 方法一：贪心具体做法：利用贪心思想，利用一个辅助数组每次操作前记录相邻两个数组之差，并找到差的最大值 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 CroMarmot
发表于 2021-10-04 23:29:07
题意 给一个有初始值的数组，并且其中每个位置单独限定最大值。 每次操作可以给任意一个位置在[0~最大值]的范围内加一减一 问在不超过k次操作后，相邻项的差的平方的最大值，最小为多少 算法 动态规划（TLE） 首先，虽然题目求的是相邻项差的平方的最大值的最小值。实际上绝对值越大平方越大，所以我们可以改 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛一霸
发表于 2021-08-15 17:28:40
取球放球 问题描述：有n个箱子，第i个箱子一开始有a_i个球，你可以进行最多k次操作，每次操作可以从一个箱子拿走一个球或者放入一个球。第i个箱子最多能装w_i个球，装满了之后不能再往这个箱子里面放球。如果一个箱子为空，就不能从里面拿球。 设相邻箱子的球的数量的差的平方中的最大值为x，求进行最 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 球球了给孩子一个offer吧
发表于 2021-08-11 12:04:20
题目：将题目换成另一个说法就是有n个数，可以对这n个数调整k次，每次只能对一个数加一或者减一，调整过程中，保持 ，设相邻两数的差的平方中的最大值为x，求调整k次后，x最小是多少 方法一：贪心 最多调整k次，因此枚举k次在开始一轮调整前，先用一个dst数组存储相邻两数的差值，,然后找出相邻两数差值的平 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 动态规划
难度：
2条回答 3022浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号