题解 | #一样的水#

思路：

题目的主要信息：

数组a是初始时水桶里的水
数组p是每次询问后，要求水桶中水相同的水桶数量
一共是q次查询，每次需要找到使水桶中拥有相同水量的水桶数量达到p中要求的最少花费，即每次加水量最少

方法一：动态规划+前缀和
具体做法：
我们用 $dp[i]$ （下标1开始）表示前i个数的和。
对于某一次查询 $i$ ，我们要求需要有 $p[i]$ 个相同水量的水桶，那我们知道经过第 $i-1$ 次查询，前面的已经相同了，所以我们后续找要添加到的标杆水桶就从下标为 $p[i]$ 开始，于是利用前面求到的前缀和，我们可以得到总花费 $sum = a[j - 1] * p[i] - (dp[j] - dp[j - p[i]])$ ，即标杆水桶的水量乘上需要相同的个数，减去前面已经有的水量（这个通过前缀和相减得到），遍历后续数组找到这个花费的最小值即可。找到之后，我们需要将标杆水桶之前的水量都修改为标杆水桶的水量，开始下一轮查询。
图片说明

class Solution {
public:
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        vector<int> res(q, 0); //q次查询的返回值
        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 Min = INT_MAX, sum = 0;
            int pos = 0; //记录修改到水一样多时的位置
            for(int j = p[i]; j <= n; j++){ //寻找最小花费时间，前面p[i]个已经相等，从后面开始找
                sum = a[j - 1] * p[i] - (dp[j] - dp[j - p[i]]);
                if(sum < Min){
                    Min = min(sum, Min);
                    pos = j;
                }
            }
            for(int j = pos - 1; j > pos - p[i]; j--) //修改pos之前的
                a[j - 1] = a[pos - 1];
            res[i] = Min;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nq+nlog_2n)$ ，外循环 $O(q)$ ，内部三个循环都是 $O(n)$ ，循环外是一个排序
空间复杂度： $O(n)$ ，只有dp是辅助空间，res属于必要空间，不算额外空间

方法二：前缀和迭代
具体做法：
方法一中的动态规划借助了辅助数组，其实我们也可以不用。每次我们使用到的前缀和只有两个，因为我们可以用迭代的方式，用变量记录在迭代中出现的前缀和，其余思路与动态规划相似。
同时，我们还可以使用一个变量记录当前最大的相同水桶数，如果当前已经满足要求，我们便可以跳过一次运算，以节省时间。

class Solution {
public:
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        vector<int> res(q, 0); 
        sort(a.begin(), a.end()); //排序
        int maxsame = 1, same = 1; 
        for (int i = 1; i < n; i++){//找出数组中大小相同并且相同个数最多的元素的个数
            if (a[i] == a[i - 1]) 
                same++;
            else {
                maxsame = max(maxsame, same);
                same = 1;
            }
        }
        int Min = 0;
        int pos = 0; //pos为标杆水桶的下标
        for (int i = 0; i < q; i++) {
            if (p[i] > maxsame) { //先与当前最大相同水桶数比较
                int sum = 0; //前p[i]个数和
                for (int j = 0; j < p[i]; j++) 
                    sum += a[j];
                Min = a[p[i] - 1] * p[i] - sum;
                pos = p[i] - 1;
                for (int j = p[i]; j < n; j++) {//遍历数组，看是否有比上面时间更短的
                    sum -= a[j - p[i]] - a[j];
                    if (Min > a[j] * p[i] - sum) { 
                        Min = a[j] * p[i] - sum;
                        pos = j;
                    }
                }
                res[i] = Min;
                for (int j = pos - p[i] + 1; j < pos; j++) //修改pos之前的
                    a[j] = a[pos];
                maxsame = p[i];
            }
        }
    return res;
}
};

复杂度分析：

时间复杂度： $O(qn+nlog_2n)$ ，外循环 $O(q)$ ，内三个循环都是 $O(n)$ ，外部计算初始最大相同数复杂度为 $O(n)$ ，相较于排序的 $O(nlgo_2n)$ 可忽略
空间复杂度： $O(1)$ ，常数个变量，res是必要空间