除以2

链接：https://ac.nowcoder.com/acm/problem/213140
来源：牛客网

首次思路：在遍数限制范围内，每次都把数组内最大的偶数除以2，最后直接计算元素总和
但是错误在于原代码的外层循环是 for(int i=0;i<k;i++)，内层循环遍历整个数组（O(n)），整体时间复杂度是 O(k×n)。但题干中 k 最大可达 10^9，n 最大 10^5，k×n 会达到 10^14—— 这是绝对无法在规定时间内跑完的（计算机每秒最多处理 10^8 次操作），必然超时。
举个例子：若 k=10^9，原代码需要循环 10^9 次，即使每次循环只花 1 纳秒，也需要 1 秒（实际每次循环远不止 1 纳秒），更别说还要加内层的 10^5 次遍历。

import java.util.Scanner;
public class Main{
public static void main(String[] args) {
        /**
         * 除以2
         * https://ac.nowcoder.com/acm/problem/213140
         */
        //输入
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        int []a=new int [n+1];
        for(int i=1;i<=n;i++){
            a[i]=in.nextInt();
        }
        //业务逻辑
        int sum=0;
        for(int i=0;i<k;i++){//外层循环：次数
            Boolean flg=false;
            int j=1;int max_j=0; int max=0;
            for( j=1;j<=n;j++){//内存循环：数组
                if(a[j]%2!=0){//只操作偶数
                    continue;
                }
                if(a[j]>max){
                    max=a[j];
                    max_j=j;
                }
                if(max==0){
                    flg=true;
                    break;
                }
            }
            a[max_j]=max/2;
            //已经找到了最大的数
            if(flg==true)//如果所有数都等于0，直接结束循环
            {
                break;
            }
        }
        for(int i=1;i<=n;i++){
            sum+=a[i];
        }
        System.out.println(sum);
    }
}

时间复杂度高的原因在于一个大偶数可能会被操作多次，但它仍是最大的数，并不需要重复遍历数组。因此，用最大堆存储当前所有偶数，每次从堆中取出最大的偶数，计算它能被操作的 “最大次数”（直到变成奇数或 k 用尽），批量处理后更新堆和剩余操作次数，将时间复杂度从 O(k×n) 降到 O(n log n + m log n)（m 是堆的操作次数，远小于 k）

/**
     * 除以2
     * 使用堆来处理大量的数据，不会超时
     */
    public static void test3_2(){
        //使用堆的版本
        /**
         * 失败的代码使用了int类型存储总和sum和输入数据x，而通过的代码使用了long类型：
         * 当输入数据较大（例如超过int的最大值2^31-1）时，int类型会发生溢出，导致计算结果错误。
         * 题目中没有限制数据范围，使用int必然会在大数据测试用例中失败，而long能处理更大的数值范围。
         */
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        //构建最大堆
        //Greater greater=new Greater();
//        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(greater);
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((a,b)->{
            return b-a;
        });
        long sum=0,x;
        for(int i=0;i<n;i++){//循环结束就自动计算总和
            x=in.nextLong();
            if(x%2==0){
                priorityQueue.offer((int)x);//输入的数据直接存进堆里
            }

            sum=sum+x;
        }
        for(int i=0;i<k;i++){
            if(priorityQueue.isEmpty()){
                break;
            }
            int num=(int)priorityQueue.poll()/2;
            sum=sum-num;
            if(num%2==0){
                priorityQueue.offer(num);
            }
        }
        System.out.println(sum);
    }