阿里巴巴3.30笔试，只来得及做第一题
养鸡场这题，一开始用遍历的方法求最大值，结果通过为零，猜测复杂度太高，后面想到用最大堆写，代码如下，没时间调试，不知道能否ac
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
static ArrayList<Integer> list = new ArrayList<Integer>();
static int nums[];
static PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) {
return o2-o1;
};
});
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//鸡场个数
int n = sc.nextInt();
//天数
int m = sc.nextInt();
//每天增加
int k = sc.nextInt();
//每个鸡场鸡数
nums = new int[n];
int sum = 0;
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
list.add(nums[i]);
sum+=nums[i];
}
int max = 0;
for (int i = 0; i < m; i++) {
sum+=k*n;
update(k);
help(maxHeap,nums);
max = maxHeap.peek();
sum-=max*0.5;
nums[list.indexOf(max)]-=0.5*max;
}
System.out.println(sum);
sc.close();
}
private static void update(int k) {
list.clear();
for (int i = 0; i < nums.length; i++) {
list.add(nums[i]+k);
nums[i]+=k;
}
}
private static void help(PriorityQueue<Integer> queue,int nums[]) {
// TODO Auto-generated method stub
if(queue!=null) {
queue.clear();
}
for (int i = 0; i < nums.length; i++) {
queue.add(nums[i]);
}
}
}
