题解 | #一样的水#

题目：一样的水
描述：有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

解法一：
思路分析：首先我们分析题目的含义，题目中输入一共包含4个字符，n表示有n个桶，q表示有q次询问，容器a表示n个水桶中初始水的体积，容器p表示需要询问多少次以及询问的值，题目的意思也很明确，就是每询问一次，你需要保证使pi个桶中水的体积相同所花费的最少时间，因为每次1秒钟内只能添加1体积的水。
——我们以示例1为例进行上述分析：
图片说明
——通过对示例1的解析，我们明白了题目的含义，在编写程序的过程中，我们应该首先设定一个存储对象res和对数组a进行升序排序，因为升序排序之后我们可以缩短运行的时间，题目中只要求两个桶的水体积相同，没有要求具体的哪两个桶，其次我们需要遍历询问的对象，因为我们需要通过询问的对象来确定需要几个桶的水的体积相同，所以我们在此需要设定一个指针对象i（i的值为询问数组的首值），我们可以通过i来首先确定一个量，即sum_min，sum_min的值等于第i个值的量乘以i就是有i个桶的水的体积的总量，然后减去前i个数的总和，就可以得到一个初始化的量，随后只需要循环a数组中连续的i个变量进行比对，就能得到一个sum_min的值，通过 $a[start:start + i] = [a[start + i - 1]] * i$ 将数组保存好以后，再开始第二轮循环即可完成所有的值。
实例分析：
图片说明

Python核心代码：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 水桶的个数
# @param q int整型 询问的次数
# @param a int整型一维数组 n个水桶中初始水的体积
# @param p int整型一维数组 每次询问的值
# @return int整型一维数组
#
class Solution:
    def solve(self , n , q , a , p ):
        # write code here
        a.sort()#首先对a进行排序
        res = []#设置存储对象
        for i in p:#遍历询问对象
            start = 0
            sum_i = sum(a[:i])#前i项的和
            dif = sum_i
            sum_min = a[i - 1]*i - sum_i
            #计算得到前方的最小值，就是用该值的大小乘以i减去前面的i项和
            for j in range(i,n):
                dif += a[j] - a[j - i]
                if a[j] * i - dif < sum_min:#验证
                    start = j + 1 - i
                    sum_min = a[j] * i - dif
            a[start:start + i] = [a[start + i - 1]] * i#保存
            res.append(sum_min)#添加进结果中
        return res

——因为我们首先循环的是询问对象组，所以假设询问对象组有N个元素，所以需要遍历N次，因为初始化，不能保证得到的是最小的元素，所以还需要遍历其余连续的i个元素，所以其总的时间复杂度为 $O(N^2)$ 。因为需要额外的res存储询问返回值的对象，但是结果数组不计入空间复杂度，所以其空间复杂度为 $O(1)$ 。

解法二：
思路分析：上述分析，我们清楚的明白了该题目的意思，下面我们还可以首先将原先a数组中的元素做个累加，将累加和返回，然后再根据上述循环进行操作，首先设定一个存储容器的对象res和上述相同，再定义一个sum的值，用来存储和，再根据for循环进行最小值的计算，根据 $sum_min = a[j - 1] * i - (sum[j] - sum[j - i])$ 就能得到初始的最小值，和解法一的公式大致相同，最终一直更新位置，然后返回res结果值即可。
图片说明
C++核心代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 水桶的个数
     * @param q int整型 询问的次数
     * @param a int整型vector n个水桶中初始水的体积
     * @param p int整型vector 每次询问的值
     * @return int整型vector
     */
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        // write code here
        int len = a.size();//首先定义a数组的长度
        sort(a.begin(), a.end());//排序
        int sum[10005];//存储前n项和
        sum[0] = 0;
        vector<int> res;
        for(auto i: p){//以询问为循环对象
            int tmp = INT_MAX;
            for(int j = 1; j <= len; j++){//计算累加值
                sum[j] = sum[j-1] + a[j-1];
            }
            int sum_min = 0, ans = INT_MAX, pos;
            for(int j = i; j <= n; j++){//循环判断最小量
                sum_min = a[j - 1] * i - (sum[j] - sum[j - i]);//计算最小值
                if(sum_min < ans){
                    ans = sum_min;//替换
                    pos = j;
                }
            }
            for(int j = pos - 1; j >= pos - i; j--){//将位置进行更新，开始进行新的一轮
                a[j] = a[pos - 1];
            }
            res.push_back(ans);
        }
        return res;
    }
};

——该方法相比于解法一增加了循环的量，需要将数组a的值进行累加，所以时间复杂度为 $O(N^2)$ ，因为sum数组为存储量固定的数组，所以空间复杂度为 $O(1)$ 。