一样的水

普通解法：

无

最优解法：

将n个数从小到大排序，然后求前缀和（记为d）。

使p个桶中的水一样且花费最小在排序后的数组中即为使连续p个桶中的水一样，花费为，枚举所有位置，找到花费最小的位置，然后将桶中的水修改。

时间复杂度：

空间复杂度：

class Solution {
public:
    /**
     *
     * @param n int整型 水桶的个数
     * @param q int整型 询问的次数
     * @param a int整型vector n个水桶中初始水的体积
     * @param p int整型vector 每次询问的值
     * @return int整型vector
     */
    int c[100010];
    int d[100010];

    vector<int> solve(int n, int q, vector<int> &a, vector<int> &p) {
        // write code here
        sort(a.begin(), a.end());
        d[0] = 0;
        for (int i = 0; i < n; i++) {
            c[i + 1] = a[i];
        }

        int cnt = 0;
        vector<int> ret;
        ret.clear();
        int x;
        while (q--) {
            x = p[cnt++];
            for (int i = 1; i <= n; i++) {
                d[i] = d[i - 1] + c[i];
            }
            int pos, ans = 0x3f3f3f3f, sum;
            for (int i = x; i <= n; i++) {
                sum = c[i] * x - (d[i] - d[i - x]);
                if (sum < ans) {
                    ans = min(sum, ans);
                    pos = i;
                }
            }
            for (int i = pos - 1; i > pos - x; i--) {
                c[i] = c[pos];
            }
            ret.emplace_back(ans);
        }
        return ret;
    }
};