一样的水_牛客博客

一开始看错题wa了好多发。。。题目要求 1.加水量最少 2.在有多种解的时候p个桶的总水量最小。为了满足条件二，很容易想到从水量最小的桶开始加水。那如何保证加水量最少？可以枚举以 $[a_{p_i}, a_{n}]$ 为标准的情况下，最少的加水量，加水量为 $a_j * p_i - \sum_{k=j-p_i}^{j}a_k$ ，后面的求和可用前缀和数组来表示。

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 size = a.size();
        sort(a.begin(), a.end());
        int sum[10005];
        int INF = 0x3f3f3f3;
        sum[0] = 0;
        vector<int> result;
        for(auto i: p){
            int tmp = INF;
            for(int j = 1; j <= size; j++){
                sum[j] = sum[j-1] + a[j-1];
            }
            int all = 0, ans = INF, pos;
            for(int j = i; j <= n; j++){
                all = a[j - 1] * i - (sum[j] - sum[j - i]);
                if(all < ans){
                    ans = all;
                    pos = j;
                }
            }
            // 加完水后做个更新
            for(int j = pos - 1; j >= pos - i; j--){
                a[j] = a[pos - 1];
            }
            result.push_back(ans);
        }
        return result;
    }
};