题意整理：

题目给出一个数组以及一组查询，每个查询的值表示需要让数组中至少存在个大小相等的值，而答案所求的就是对于每个查询，仅对数组元素进行加1操作，需要几次操作能够满足要求。在满足最小操作次数的前提下，需要使得该相等的值最小

方法一：暴力

核心思想：

容易想到的一种思路就是：首先对数组排序，然后对于每个可能成功目标值的值，从前往后记录将其之前的个元素的值改为目标值的开销，遍历完成后取得该开销为本次查询答案，并对数组进行修改。

核心代码：

class Solution {
public:
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        vector<int> ans(q);//记录答案
        sort(a.begin(), a.end());//排序
        for(int i = 0; i < q; ++i) {
            int need = p[i];
            if(need == 1) continue;//此时不需要调整，答案为0
            int cost = 0x3F3F3F3F;//初始化开销为极大值
            int pt = 0;//记录最小开销对应的点
            for(int j = need - 1; j < n; ++j) {
                //从need-1开始枚举，因为之前的值无法作为目标值
                int res = 0;
                //统计开销
                for(int k = 1; k < need; ++k) {
                    res += (a[j] - a[j - k]);
                }
                if(res < cost) {
                    //判决
                    cost = res;
                    pt = j;
                }
            }
            ans[i] = cost;
            //根据结果修改数组
            for(int j = 1; j < need; ++j) {
                a[pt - j] = a[pt];
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：。排序开销，使用了三重循环开销为
空间复杂度：,一般返回的答案数组不计入空间复杂度，而除该数组外只使用了常数个变量

方法二：前缀和

核心思想：

可以发现，方法一中的代码中的第三个for循环可以视为是对一个区间中的数求和，通常这可以使用前缀和进行优化，实现的求和，使得时间复杂度下降。

核心代码：

class Solution {
public:
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        vector<int> ans(q);//记录答案
        sort(a.begin(), a.end());//排序
        vector<int> sum(n + 1);
        for(int i = 1; i < n; ++i) {
            //构造前缀数组
            sum[i] = a[i - 1] + sum[i - 1];
        }
        for(int i = 0; i < q; ++i) {
            int need = p[i];
            if(need == 1) continue;//此时不需要调整，答案为0
            int cost = 0x3F3F3F3F;//初始化开销为极大值
            int pt = 0;//记录最小开销对应的点
            for(int j = need - 1; j < n; ++j) {
                //从need-1开始枚举，因为之前的值无法作为目标值
                int res = a[j] * (need - 1) - (sum[j] - sum[j - need + 1]);
                if(res < cost) {
                    //判决
                    cost = res;
                    pt = j;
                }
            }
            ans[i] = cost;
            //根据结果修改数组
            for(int j = pt - need + 1; j < pt; ++j) {
                a[j] = a[pt];
            }
            for(int j = pt - need + 1; j < n; ++j) {
                sum[j + 1] = sum[j] + a[j];
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：，排序开销，使用了二重循环开销为
空间复杂度：,即为前缀和数组的开销

方法三：前缀和+查询优化

核心思想：

对于方法二还有优化的空间，对于单个查询,操作后会使得数组中最少存在个相同元素，所以在其之后的小于等于的查询可以直接返回0

核心代码：

class Solution {
public:
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        vector<int> ans(q);//记录答案
        sort(a.begin(), a.end());//排序
        vector<int> sum(n + 1);
        for(int i = 1; i < n; ++i) {
            //构造前缀数组
            sum[i] = a[i - 1] + sum[i - 1];
        }
        int now = 1;
        for(int i = 0; i < q; ++i) {
            int need = p[i];
            if(need <= now) continue;//此时不需要调整，答案为0
            now = need;
            int cost = 0x3F3F3F3F;//初始化开销为极大值
            int pt = 0;//记录最小开销对应的点
            for(int j = need - 1; j < n; ++j) {
                //从need-1开始枚举，因为之前的值无法作为目标值
                int res = a[j] * (need - 1) - (sum[j] - sum[j - need + 1]);
                if(res < cost) {
                    //判决
                    cost = res;
                    pt = j;
                }
            }
            ans[i] = cost;
            //根据结果修改数组
            for(int j = pt - need + 1; j < pt; ++j) {
                a[j] = a[pt];
            }
            for(int j = pt - need + 1; j < n; ++j) {
                sum[j + 1] = sum[j] + a[j];
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：，排序开销，使用了二重循环开销为
空间复杂度：,即为前缀和数组的开销