Javascript: tìm tổng nhỏ nhất sau k phép toán

Question

Một mảng được thao tác k lần để mỗi lần giá trị lớn nhất được chia cho 2 và làm tròn lên. Tôi cần tìm tổng tối thiểu của nó sau k thao tác này. k và tất cả các số trong mảng num> 1. Phương thức minSum nhận một mảng gọi là num và một số nguyên k. Mã Python thô bạo hoạt động với tôi với độ phức tạp về thời gian rất tệ là:

function minSum(arr, k) {
    // Write your code here
let sum = 0; 
    while(k !==0){

       
        let max = Math.max(...arr)
        let index = arr.indexOf(max);
         
        max = Math.ceil(max/2);
        arr[index] = max;
        
        k--;
    }
    sum =  arr.reduce((a, b) => a + b, 0);
        console.log(sum);
    return sum;
}

Câu hỏi tương tự liên quan đến python là ở đây. Phương pháp hiệu quả hơn để tìm tổng nhỏ nhất sau k phép toán

nhưng không có gì liên quan đến Javascript.

Answer 1

Dưới đây là các bước (sử dụng Java dựa trên nhu cầu đầu tiên của bạn trước khi thay đổi sang JavaScript):

• 1. Sử dụng đống tối đa (PriorityQueue theo thứ tự ngược lại), do đó giá trị tối đa sẽ ở trên cùng.
• 1. Đối với k lần lặp: lấy phần tử ở trên cùng (thăm dò ()), thực hiện thao tác và thêm lại phần tử đó vào đống tối đa.
• 1. Cuối cùng, chỉ cần tổng hợp.

    public static int minSumJava_using_pqueue(int arr[], int k)
    {
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());

        for (int val : arr) {
            pq.add(val);
        }

        int new_val;
        for(int i =0; i<k; i++)
        {
            new_val = pq.poll();
            new_val = (int) Math.ceil(new_val/2.0);
            pq.add(new_val);
        }

        int sum = 0;
        for (Integer val: pq) {
            sum += val;
        }
        
        return sum;
    }

Kiểm tra mã nguồn:

    public static void main(String[] args)
    {
        int k = 4;
        int arr[] = {10,20,7};
        int result = minSumJava_using_pqueue(arr, k);
        System.out.println("min sum = "+ result);
    }

Kết quả thực sự giống như trong ví dụ của bạn:

min sum = 14

Lưu ý: bạn có thể thực hiện chính xác điều tương tự với JavaScript hoặc bất kỳ ngôn ngữ lập trình nào khác .