题解 | #一样的水#

题目描述
有n个水桶，第i个水桶里面水的体积为Ai，你可以用1秒时间向一个桶里添加1体积的水。
有q次询问，每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。
对于一次询问如果有多种方案，则采用使最终pi个桶中水的体积最小的方案。

方法一：动态规划的思想

求解思路
对于求解本题目，我们可以使用动态规划的思想，我们用dp[i]表示前i个数的和。对于题目所提到的每次询问，我们看成第i次查询的说法。我们要求需要有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> myres(q, 0); // 记录结果
        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--)
                a[j - 1] = a[pos - 1];
            myres[i] = Min;
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用dp数组，引入额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：迭代的思想

求解思路
对于方法一，我们对其进行改进，在每次迭代的过程中，我们用变量记录其前缀和，而不是使用方法一的辅助数组，其余的操作和方法一相同，并得到最终的答案。

图片说明

解题代码

class Solution {
public:
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p)
    {
        vector<int> myres(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;
        for (int i = 0; i < q; i++)
        {
            if (p[i] > maxsame) 
            {   //先与当前最大相同水桶数比较
                int sum = 0;
                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;
                    }
                }
                myres[i] = Min;
                for (int j = pos - p[i] + 1; j < pos; j++) // 修改pos之前的
                    a[j] = a[pos];
                maxsame = p[i];
            }
        }
    return myres; // 返回结果
}
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：没有引入额外的内存地址空间，因此空间复杂度为 $O(1)$