有n个水桶,第i个水桶里面水的体积为Ai,你可以用1秒时间向一个桶里添加1体积的水。
有q次询问,每次询问一个整数pi,你需要求出使其中pi个桶中水的体积相同所花费的最少时间。 对于一次询问如果有多种方案,则采用使最终pi个桶中水的体积最小的方案。
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≤1041≤q≤5001≤Ai≤1042≤pi≤n
//感谢勤奋小牛牛的语法帮助 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))); } }