一样的水

问题描述：有n个水桶，第i个水桶里面水的体积为$A_{i}$，你可以用1秒时间向一个桶里添加1体积的水。有q次询问，每次询问一个整数$p_{i}$,你需要求出使其中$p_{i}$个桶中水的体积相同所花费的最少时间。对于一次询问如果有多种方案，则采用使最终$p_{i}$个桶中水的体积最小的方案。
示例
输入：4,3,[1,2,3,4],[2,2,4]
返回值：[1,0,5]
说明：
第一次：花费一秒变为 2 2 3 4

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

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

方法一

思路分析

     显然本题为了得到最小的操作时间以及最后最小的总体积，先将存储水的数组进行升序排序，然后对于每一次的操作有如下过程：
  • 首先每一次操作均会提供一个整数$p[i]$，用于表示需要使$p[i]$个桶中的水的体积相同，且时间最小
  • 从数组开始元素出发，设置滑动窗口，窗口的长度为$p[i]$，即使得$[0,1,...p[i]]$之间的水桶中的水的体积相同，$time=a[p[i]-1]*p[i]-(a[0]+a[1]…+a[p[i]])$
  • 接着窗口向后滑动一个长度，此时增加的元素为$a[s]$，此时的时间增量为增加的元素带来的时间增值$increase=（a[s]-a[s-1]）*(len-1)$，而滑出去的最左边的元素所带来的减值$reduce=a[s-1]-s[s-p[i]]$
  • 该次操作的$time=time+increase-reduce$，不断的向后滑动窗口，将最小的$time$记录下来，并将改变的位置记录，循环结束后，改变时间最小的那一次需要增加的水的体积的元素
  • 接着进行下一次的操作过程。

图解



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
        vector<int> res;
        sort(a.begin(),a.end());//排序
        //滑动窗口
        for(int i=0;i<q;i++)
        {
            
            int len=p[i];//滑动窗口的长度
            int ans=0;//标记下标
            int time=a[len-1]*len;
            for(int j=0;j<len;j++)
                time-=a[j];
            int min=time;//开始时的最少时间
            int increase=0;
            int reduce=0;
            for(int i=len;i<n;i++) 
            {
                increase=(a[i]-a[i-1])*(len-1);//向后滑动一个窗口增加的元素带来的时间增值
                reduce=a[i-1]-a[i-len];//滑出去的最左边的元素所带来的减值
                time+=increase-reduce;
                if(time<min)
                {
                    min=time;
                    ans=i-len+1;//记录需要改变的开始位置
                }               
            }  
            for(int i=ans;i<ans+len;i++)
                a[i]=a[ans+len-1];  //最少时间方案以及记录的开始元素位置调整桶的水的体积          
            res.push_back(min);
        }     
        return res;  
    }
};

复杂度分析

  • 时间复杂度：开始时需要对数组进行sort排序，时间复杂度为$O(n\log n)$。内外两层循环，外层表示需要操作的次数$q$，内层循环为滑动窗口的次数，最坏情况下滑动次数为数组的长度$n$，因此时间复杂度为$O(nq+n\log n)$
  • 空间复杂度：借助于一个大小为$q$的数组，因此空间复杂度为$O(q)$


方法二

思路分析

    根据方法一，对数组$a$求取前缀和，每一次的操作为如下过程：
  • 设置$dp[j]$表示数组元素中前$j-1$个的和
  • 每一次长度为$len$的数组元素需要添加的水为$a[j-1]*len-(a[j-1]+a[j-2] ..+ a[j – len-1])=a[j-1]*len-(dp[j] - dp[j - len])$

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
        vector<int> res;
		vector<int> dp(n+1,0);
        sort(a.begin(),a.end());//排序
        for(int i=0;i<q;i++)//遍历操作数组
        {
			for(int j = 1; j <= n; j++)
                dp[j] = dp[j - 1] + a[j - 1]; //计算前缀和
            int len=p[i];//滑动窗口的长度
            int index=0;//标记下标
            int min=INT_MAX;//最少时间
			int time=0;
            for(int j=len;j<=n;j++) 
            {
                time=a[j-1]*len-(dp[j] - dp[j - len]);//长度为len需要增加的水
                if(time<min)
                {
                    min=time;
                    index=j;
                }               
            } 
            //结束之后  按照最少时间方案调整桶 
            for(int s=index-1;s>index-len;s--)
                a[s-1]=a[index-1];          
            res.push_back(min);
        }     
        return res;  
    }
};

复杂度分析

  • 时间复杂度：开始时需要对数组进行sort排序，时间复杂度为$O(n \log n)$。内外两层循环，外层表示需要操作的次数$q$，内层循环最坏情况下循环次数为数组的长度$n$，因此时间复杂度为$O(nq+n\log n)$
  • 空间复杂度：借助于一个大小为$q$的数组用于存储每次操作的结果，借助于一个大小为$n+1$的前缀和数组，因此空间复杂度为$O(n+q)$