首页 > 试题广场 >

一样的水

[编程题]一样的水
  • 热度指数：3855 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
有n个水桶，第i个水桶里面水的体积为Ai，你可以用1秒时间向一个桶里添加1体积的水。
有q次询问，每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。
对于一次询问如果有多种方案，则采用使最终pi个桶中水的体积最小的方案。

示例1

输入

4,3,[1,2,3,4],[2,2,4]

输出

[1,0,5]

说明

第一次：花费一秒变为 2 2 3 4

第二次：已经存在两个水的体积一样的桶

第三次：花费五秒从2 2 3 4变为4 4 4 4


备注:
2≤n≤104
1≤q≤500
1≤Ai≤104
2≤pi≤n
算法知识视频讲解
开通博客
头像 Enast
发表于 2020-04-02 16:06:33
按照别人的思路画了个图解:其他的询问值也是类似处理. public int[] solve (int n, int q, int[] a, int[] p) { // write code here // 询问一次p的意思是要有p个桶的体积一样 // 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 大碗饭加蛋
发表于 2020-03-24 18:36:19
一开始看错题wa了好多发。。。题目要求 1.加水量最少 2.在有多种解的时候p个桶的总水量最小。为了满足条件二，很容易想到从水量最小的桶开始加水。那如何保证加水量最少？可以枚举以 为标准的情况下，最少的加水量，加水量为 ，后面的求和可用前缀和数组来表示。 class Solution { publ 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 电玩码子
发表于 2022-02-12 23:13:52
暴力编码过于复杂，建议看代码注释 暴力解题方式，梅什么 好说的。 先排序，方便计算。因为要时间最少，肯定是取数量连续的水桶。所以排序好。 然后通过多重循环取要均等的Pi个水桶，重A0开始遍历所有的连续值场景生成这些场景的水桶数组，并计算均等她它们需要的时间，循环结束后如果时间变小了，存入返回数组中。 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-07-31 15:16:58
题目描述有n个水桶，第i个水桶里面水的体积为Ai，你可以用1秒时间向一个桶里添加1体积的水。有q次询问，每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。对于一次询问如果有多种方案，则采用使最终pi个桶中水的体积最小的方案。 方法一：动态规划的思想 求解思路对于求解本题目 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 泪无声呢
发表于 2021-08-06 16:25:37
一样的水 问题描述：有n个水桶，第i个水桶里面水的体积为$A_{i}$，你可以用1秒时间向一个桶里添加1体积的水。有q次询问，每次询问一个整数$p_{i}$,你需要求出使其中$p_{i}$个桶中水的体积相同所花费的最少时间。对于一次询问如果有多种方案，则采用使最终$p_{i}$个桶中水的体积最 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 changed.
发表于 2021-09-21 14:34:13
题意整理： 题目给出一个数组以及一组查询，每个查询的值表示需要让数组中至少存在个大小相等的值，而答案所求的就是对于每个查询，仅对数组元素进行加1操作，需要几次操作能够满足要求。在满足最小操作次数的前提下，需要使得该相等的值最小 方法一：暴力 核心思想： 容易想到的一种思路就是：首先对数组排序，然后对 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 Albert333
发表于 2020-02-05 13:41:52
普通解法： 无 最优解法： 将n个数从小到大排序，然后求前缀和（记为d）。 使p个桶中的水一样且花费最小在排序后的数组中即为使连续p个桶中的水一样，花费为，枚举所有位置，找到花费最小的位置，然后将桶中的水修改。 时间复杂度： 空间复杂度： class Solution { public: 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛一霸
发表于 2021-08-08 23:09:03
题目：一样的水描述：有n个水桶，第i个水桶里面水的体积为Ai，你可以用1秒时间向一个桶里添加1体积的水。有q次询问，每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。对于一次询问如果有多种方案，则采用使最终pi个桶中水的体积最小的方案。示例1：输入：4,3,[1,2,3, 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-07-30 13:52:09
思路： 题目的主要信息： 数组a是初始时水桶里的水 数组p是每次询问后，要求水桶中水相同的水桶数量 一共是q次查询，每次需要找到使水桶中拥有相同水量的水桶数量达到p中要求的最少花费，即每次加水量最少 方法一：动态规划+前缀和具体做法：我们用（下标1开始）表示前i个数的和。对于某一次查询，我们要求 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

数组 查找
难度：
10条回答 4767浏览

热门推荐

通过挑战的用户

查看代码

相关试题

一样的水

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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