阿里3.30笔试第一题
题目就不说了，其他地方也有，我觉得关键是要自己实现一个大顶堆，如果只用Java.Util包的PriorityQueue，并没有提供直接修改堆内数据的接口，所以要每个元素增加k的话，就要把元素全部弹出来放数组，加完再放回去，我今天这样做然后就超时了😪😪，痛定思痛地回去用数组自己实现了个堆去解。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int k = sc.nextInt();
int[] arr = new int[n];
int ans = 0;
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
BuildHeap(arr);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)//这里可以在堆中直接遍历增加k
arr[j] += k;
arr[0]/=2;//取堆顶元素除以2
Heapify(arr,0,n);//再次调整堆
}
for(int i:arr)
ans+=i;
System.out.println(ans);
}
//建立大顶堆
public static void BuildHeap(int[] arr){
for(int i=arr.length/2;i>=0;i--){
Heapify(arr,i,arr.length);
}
}
//调整堆
public static void Heapify(int[] arr,int i ,int len){
int left = i*2+1;
int right = i*2+2;
int largest = i;
if(left<len && arr[left]>arr[largest]) largest = left;
if(right<len && arr[right]>arr[largest]) largest = right;
if(largest!=i){
swap(arr,i,largest);
Heapify(arr,largest,len);
}
}
public static void swap(int[] arr , int a , int b) {
int t = arr[a];arr[a]=arr[b];arr[b]=t;
} 如有错误，希望大佬指正！！