Javascript: menemukan jumlah minimum setelah operasi k

Question

Sebuah array dimanipulasi k kali sehingga setiap kali nilai maksimal dibagi 2 dan dibulatkan. Saya perlu menemukan jumlah minimumnya setelah manipulasi k ini. k dan semua bilangan dalam array num> 1. Metode minSum menerima sebuah array yang disebut num dan integer k. Kode Python kasar yang bekerja untuk saya dengan kompleksitas waktu yang sangat buruk adalah:

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

Pertanyaan serupa terkait dengan python ada di sini. Metode yang lebih efisien untuk menemukan jumlah minimum setelah operasi k

tapi tidak ada yang berhubungan dengan Javascript.

Answer 1

Berikut langkah-langkahnya (menggunakan Java berdasarkan permintaan pertama Anda sebelum beralih ke JavaScript):

• 1. Gunakan tumpukan maks (Antrian Prioritas dalam urutan terbalik), jadi maks akan berada di atas.
• 1. Untuk iterasi k: dapatkan elemen di atas (poll ()), lakukan operasi, dan tambahkan lagi ke heap maks.
• 1. Pada akhirnya, jumlahkan saja.

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

Periksa kode sumbernya:

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

Hasilnya memang sama dengan contoh Anda:

min sum = 14

Catatan: Anda dapat melakukan hal yang persis sama dengan JavaScript atau bahasa pemrograman lainnya .