一样的水

[编程题]一样的水

热度指数：3847 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

有n个水桶，第i个水桶里面水的体积为A_i，你可以用1秒时间向一个桶里添加1体积的水。

有q次询问，每次询问一个整数p_i,你需要求出使其中p_i个桶中水的体积相同所花费的最少时间。

对于一次询问如果有多种方案，则采用使最终p_i个桶中水的体积最小的方案。

示例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≤10⁴
1≤q≤500
1≤A_i≤10⁴
2≤p_i≤n

算法知识视频讲解

Python 3

ZhongHaoWang

首先将a排序,我们可以知道,最少的操作时间一定是对于相邻的p[i]个水桶,因此我们对于每次查询,去遍历整个a数组,得到最少操作时间的区间,并将a数组修改即可,每次遍历a我们可以在O(1)时间得到每个区间对应的最小花费时间

class Solution:
    def solve(self , n , q , a , p ):
        # write code here
        ans = []
        a.sort()
        
        # 获取最小操作区间
        def getminop(x):
            l,r = 0,x - 1
            v = 0
            for i in range(x):
                v += a[i]
            v = x * a[x - 1] - v
            cost = v
            for i in range(x,n):
                cost = cost + (x * a[i] - a[i]) + a[i - x] - x * (a[i - 1])
                if cost < v:
                    v = cost
                    l,r = i - x + 1,i
            return l,r,v
            
        for i in range(q):
            if p[i] == 1:
                ans.append(0)
                continue
            l,r,v = getminop(p[i])
            ans.append(v)
            for i in range(l,r + 1):
                a[i] = a[r]
        return ans

发表于 2021-08-28 10:59:30 回复(0)