首页 > 试题广场 >

一样的水

[编程题]一样的水
  • 热度指数:3847 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
有n个水桶,第i个水桶里面水的体积为Ai,你可以用1秒时间向一个桶里添加1体积的水。
有q次询问,每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。
对于一次询问如果有多种方案,则采用使最终pi个桶中水的体积最小的方案。

示例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≤104
1≤q≤500
1≤Ai≤104
2≤pi≤n
求救啊 怎么写输入那部分
scanner
发表于 2020-04-11 20:42:57 回复(0)
//感谢勤奋小牛牛的语法帮助
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)