首页 > 试题广场 >

一样的水

[编程题]一样的水

热度指数：3847 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

有n个水桶，第i个水桶里面水的体积为A_i，你可以用1秒时间向一个桶里添加1体积的水。

有q次询问，每次询问一个整数p_i,你需要求出使其中p_i个桶中水的体积相同所花费的最少时间。

对于一次询问如果有多种方案，则采用使最终p_i个桶中水的体积最小的方案。

示例1

输入

4,3,[1,2,3,4],[2,2,4]

输出

[1,0,5]

说明

第一次：花费一秒变为 2 2 3 4

第二次：已经存在两个水的体积一样的桶

第三次：花费五秒从2 2 3 4变为4 4 4 4

备注:

2≤n≤10⁴
1≤q≤500
1≤A_i≤10⁴
2≤p_i≤n

算法知识视频讲解

C/C++

nbgao

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) {
        vector<int> r;
        sort(a.begin(), a.end());
        for(auto &x: p){
            int s = (x-1)*a[x-1], l=x-1;
            for(int i=0;i<x-1;i++)
                s -= a[i];
            int Min = s;
            for(int i=x;i<n;i++){
                s += (x-1)*(a[i]-a[i-1])-(a[i-1]-a[i-x]);
                if(s < Min){
                    Min = s;
                    l = i;
                }
            }
            for(int i=l-x+1;i<l;i++)
                a[i] = a[l];
            r.push_back(Min);
        }
        return r;
    }
};

发表于 2020-08-05 01:13:23 回复(0)

Java

牛客104426236号

//感谢勤奋小牛牛的语法帮助
package Day1;  
  
import java.util.ArrayList;  
import java.util.Arrays;  
  
public class Solution {  
    /** 
     *  
     * @param n int整型 水桶的个数 
     * @param q int整型 询问的次数 
     * @param a int整型一维数组 n个水桶中初始水的体积 
     * @param p int整型一维数组 每次询问的值 
     * @return int整型一维数组 
     */  
    public int[] solve (int n, int q, int[] a, int[] p) {  
        // write code here  
        int m[] = new int[q];  
        Arrays.sort(a);  
        for (int i = 0; i < p.length; i++) {  
            int a1 = 0;    
            ArrayList<Integer> A = new ArrayList<Integer>();    
            for (int j = 0; j < a.length; j++) {    
                a1 = a1 + a[j];    
                A.add(a1);    
            }  
            int best_w = (int) 10E8;  
            int best_j = 0;  
  
            for (int j = 0; j < a.length-p[i]+1; j++) {  
                int w = a[j+p[i]-1]*(p[i]-1) - (A.get(j+p[i]-2)-A.get(j)+a[j]);   
                  
                if (w < best_w) {  
                    best_w = w;  
  
                    best_j = j;  
                }  
            }  
            m[i] = best_w;  
              
            for (int j = best_j; j < best_j + p[i]; j++) {  
                a[j] = a[best_j + p[i] - 1];  
            }  
        }  
  
        return m;  
    }  
    public static void main(String[] args) {  
        int n = 50;  
        int q = 10;  
        int a[] = {278,125,679,818,337,683,245,67,922,43,310,505,254,951,378,733,373,643,170,632,711,766,256,620,570,51,494,907,388,126,580,823,485,693,969,931,209,455,533,414,318,777,862,102,742,257,550,706,492,968};  
        int p[] = {28,15,19,38,27,13,23,38,11,30};   
        Solution s = new Solution();  
        System.out.println(Arrays.toString(s.solve(n, q, a, p)));  
    }  
  
}

发表于 2020-04-08 01:34:14 回复(0)

果咩纳塞牛

public class Solution {
    public int[] solve (int n, int q, int[] a, int[] p) {
        // 定义一个数组m用于存储每个询问的答案
        int[] ans = new int[q];
        // 对桶的水量进行排序
        Arrays.sort(a);
        for (int i = 0; i < p.length; i++) {
            int a1 = 0;
            ArrayList<Integer> A = new ArrayList<>();
            // 计算前缀和数组A，其中A[i]表示前i个桶的水量之和
            for (int j = 0; j < a.length; j++) {
                a1 = a1 + a[j];     //这里没有前导0,
                A.add(a1);
            }
            int best_w = (int) 10E8;//integer.max_value
            int best_j = 0;

            // 枚举起始的桶j，计算添加水量使得p[i]个桶中的水量相等所需的最小时间
            for (int j = 0; j < a.length-p[i]+1; j++) {
                //a[j+p[i]-1]*(p[i]-1)就是添加水量所需的时间
                // (A.get(j+p[i]-2) - A.get(j) + a[j])表示这些桶中当前已经有多少水了，需要减去这部分水的贡献。
                int w = a[j+p[i]-1]*(p[i]-1) - (A.get(j+p[i]-2)-A.get(j)+a[j]);
                if (w < best_w) {
                    best_w = w;  //最小的时间
                    best_j = j; //最优的起始桶位置
                }
            }
            // 将当前的p[i]个桶的水量全部设为最大水量
            for (int j = best_j; j < best_j + p[i]; j++) {
                a[j] = a[best_j + p[i] - 1];
            }
            // 将当前询问的答案记录在数组m中
            ans[i] = best_w;
        }
        return ans;
    }


    public static void main(String[] args) {
        int n = 50;
        int q = 10;
        int a[] = {278,125,679,818,337,683,245,67,922,43,310,505,254,951,378,733,373,643,170,632,711,766,256,620,570,51,494,907,388,126,580,823,485,693,969,931,209,455,533,414,318,777,862,102,742,257,550,706,492,968};
        int p[] = {28,15,19,38,27,13,23,38,11,30};
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.solve(n, q, a, p)));
    }

}

发表于 2023-05-16 11:37:57 回复(0)

Python 3

ZhongHaoWang

首先将a排序,我们可以知道,最少的操作时间一定是对于相邻的p[i]个水桶,因此我们对于每次查询,去遍历整个a数组,得到最少操作时间的区间,并将a数组修改即可,每次遍历a我们可以在O(1)时间得到每个区间对应的最小花费时间

class Solution:
    def solve(self , n , q , a , p ):
        # write code here
        ans = []
        a.sort()
        
        # 获取最小操作区间
        def getminop(x):
            l,r = 0,x - 1
            v = 0
            for i in range(x):
                v += a[i]
            v = x * a[x - 1] - v
            cost = v
            for i in range(x,n):
                cost = cost + (x * a[i] - a[i]) + a[i - x] - x * (a[i - 1])
                if cost < v:
                    v = cost
                    l,r = i - x + 1,i
            return l,r,v
            
        for i in range(q):
            if p[i] == 1:
                ans.append(0)
                continue
            l,r,v = getminop(p[i])
            ans.append(v)
            for i in range(l,r + 1):
                a[i] = a[r]
        return ans

发表于 2021-08-28 10:59:30 回复(0)

牛客405657064号

fhvvc

发表于 2021-04-21 13:10:44 回复(0)

C/C++

.晚安

class Solution {
public:
    /**
     * 
     * @param n int整型 水桶的个数
     * @param q int整型 询问的次数
     * @param a int整型vector n个水桶中初始水的体积
     * @param p int整型vector 每次询问的值
     * @return int整型vector
     */
    int f(int n, vector<int>& a, int p) {
        int t = (p - 1) * a[p - 1];
        for (int i = 0; i < p - 1; i++) t -= a[i];
        int Min = t, I = p - 1;
        for (int i = p; i < n; i++) {
            t += (p - 1) * (a[i] - a[i - 1]) - (a[i - 1] - a[i - p]);
            if (t < Min) {
                Min = t;
                I = i;
            }
        }
        for (int i = I - 1; i > I - p; i--) a[i] = a[I];
        return Min;
    }
    
    vector<int> solve(int n, int q, vector<int>& a, vector<int>& p) {
        sort(a.begin(), a.end());
        vector<int> b;
        for (int i = 0; i < q; i++) b.push_back(f(n, a, p[i]));
        return b;
    }
};

发表于 2020-07-26 21:15:46 回复(0)

萨巴鲁酱

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
        vector<int> res;
        vector<int> water(a);
        sort(water.begin(), water.end());
        for(int num : p){
            int sum = 0, min = 0, j = 0;
            for(int i = 0; i < num; ++i)
                sum += water[i];
            min = water[num-1] * num - sum;
            
            for(int i = 1; i + num <= n; ++i){
                sum += water[i+num-1] - water[i-1];
                int temp = water[i+num-1] * num - sum;
                if(temp < min){
                    j = i;
                    min = temp;
                }
            }
            
            for(int i = j; i < j + num - 1; ++i)
                water[i] = water[j+num-1];
            res.push_back(min);
        }
        return res;
    }
};

发表于 2020-05-19 00:30:01 回复(0)

牛客4061663号

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
vector<int> ret;
vector<int> a2(a);
sort(a2.begin(), a2.end());

for(int i=0; i<q; ++i){
int min_t = INT_MAX;
int end_index;
for(int j=p[i]-1; j<n; ++j){
int tmp_t = (p[i]-1)*a2[j] - accumulate(a2.begin()+j-p[i]+1, a2.begin()+j, 0);
if(tmp_t < min_t){
min_t = tmp_t;
end_index = j;
}
//cout<<tmp_t<<" "<<end_index<<endl;
}
ret.push_back(min_t);
for(int j=end_index; j>=end_index-p[i]+1; --j)
a2[j] += a2[end_index] - a2[j];
}

return ret;
}

};

一样的思路，用accumulate函数简化了一个循环

发表于 2020-04-29 12:44:19 回复(0)

Java

牛客646875505号

求救啊怎么写输入那部分

scanner

发表于 2020-04-11 20:42:57 回复(0)

offerPlusPlus_

public int[] solve (int n, int q, int[] a, int[] p) {
        // write code here
        int[] res=new int[q];
        Arrays.sort(a);
        for (int i = 0; i < q; i++) {
            int[] sumA=new int[n];
            sumA[0]=a[0];
            for (int x = 1; x < n; x++) {
                sumA[x]=sumA[x-1]+a[x];
            }
            int time=Integer.MAX_VALUE;
            int num=Integer.MAX_VALUE;
            int index=0;
            for (int j = 0; j <= n-p[i]; j++) {
                int tempTime=a[j+p[i]-1]*(p[i]-1)-(sumA[j+p[i]-2]-sumA[j]+a[j]);
                int tempNum=a[j+p[i]-1]*p[i];
                if(tempTime==0){
                    res[i]=0;
                    time=0;
                    break;
                }else if(tempTime<time){
                    time=tempTime;
                    num=tempNum;
                    index=j;
                }else if(tempTime==time&&tempNum<num){
                    time=tempTime;
                    num=tempNum;
                    index=j;
                }
            }
            if(time!=0){
                res[i]=time;
                for (int k = index; k < index+p[i]; k++) {
                    a[k]=a[index+p[i]-1];
                }
            }
        }
        return res;
    }

对于查询qi，依次遍历a数组，检查a[j]及之后到a[j+qi-1]所组成的qi个桶是不是满足使得其中pi个桶中水的体积相同所花费的最少时间。

发表于 2020-03-26 11:23:52 回复(0)