阿里3.30笔试第一题

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;
}