Jumlah maksimum tatasusunan yang mungkin selepas melakukan operasi yang diberikan

Dalam soalan ini, kami akan melaksanakan operasi yang diberikan pada elemen tatasusunan dan mencari jumlah maksimum akhir.

Di sini, dalam setiap operasi, kita boleh memilih paling banyak elemen X[p] daripada tatasusunan dan menggantikannya dengan elemen Y[p] untuk memaksimumkan jumlah.

Dalam kaedah mudah kita akan mencari elemen tatasusunan X[p] yang lebih kecil daripada elemen Y[p] dan menggantikannya dengan Y[p].

Dalam pendekatan yang cekap kami akan menggunakan baris gilir keutamaan untuk mendapatkan jumlah maksimum.

Pernyataan Masalah− Kami diberi tatasusunan nums[] yang mengandungi N nombor. Pada masa yang sama, kita diberikan tatasusunan X[] dan Y[] yang mengandungi integer M. Kita perlu melakukan operasi berikut pada tatasusunan nums[].

• Kita perlu melakukan operasi M pada setiap elemen X[] dan Y[]. Dalam setiap operasi, kita perlu memilih elemen X[p] terbesar daripada nombor tatasusunan[] dan menggantikannya dengan Y[p].

Tugas yang diberikan ialah mencari jumlah maksimum unsur tatasusunan nums[] selepas melakukan operasi M.

Contoh Contoh

Masuk

nums[] = {10, 8, 7, 60, 20, 18, 30, 60}; m = 3; x[] = {1, 2, 5}; y[] = {500, 10, 2};

Output

708

Penjelasan − Mari lakukan setiap operasi satu persatu.

• Dalam operasi pertama, kami akan menggantikan 7 elemen dengan 500. Jadi, tatasusunan menjadi {10, 8, 500, 60, 20, 18, 30, 60}.

• Dalam operasi kedua, kita boleh menggantikan sehingga 2 elemen dengan 10, tetapi kita hanya mempunyai 1 elemen kurang daripada 10. Jadi, kita gantikan 8 dengan 10 dan tatasusunan menjadi {10, 10, 500, 60, 20, 18, 30, 60}.

• Dalam operasi ketiga, kita boleh menggantikan sehingga 5 elemen dengan 2, tetapi tiada unsur kurang daripada 2 dalam tatasusunan. Oleh itu, kami tidak akan menggantikan mana-mana elemen.

Masuk

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 3, 6}; y[] = {10, 8, 21};

Output

230

Penjelasan − Semua elemen tatasusunan y[] adalah lebih kecil daripada unsur tatasusunan asal. Oleh itu, kita tidak perlu menggantikan mana-mana elemen tatasusunan yang diberikan untuk mendapatkan jumlah maksimum.

Masuk

nums[] = {30, 40, 50, 50, 60}; m = 3; x[] = {2, 4, 5}; y[] = {50, 60, 100};

Output

500

Penjelasan − Di sini, kita boleh menggantikan sehingga x[p] elemen dalam setiap operasi. Dalam operasi terakhir, kita boleh menggantikan setiap elemen dalam tatasusunan dengan 100, menghasilkan jumlah maksimum yang sama dengan 100.

Kaedah 1

Dalam kaedah ini, kami akan mengulangi tatasusunan x[] dan y[]. Dalam setiap lelaran, kami akan mengisih tatasusunan untuk mendapatkan paling banyak unsur tatasusunan x[p] yang lebih kecil daripada elemen y[p] dan menggantikannya dengan y[p].

Algoritma

Langkah 1 − Mulakan 'maxSum' kepada 0, yang digunakan untuk menyimpan jumlah maksimum elemen tatasusunan.

Langkah 2 − Mula melintasi elemen tatasusunan x[] dan y[].

Langkah 3 − Simpan nilai x[p] ke dalam pembolehubah sementara dan susun tatasusunan nums[].

Langkah 4− Mula melintasi tatasusunan yang diisih dalam gelung.

Langkah 5 − Jika suhu lebih besar daripada 0 dan nums[q] kurang daripada y[p], kemas kini nombor[q] dengan y[p] dan kurangkan nilai temp sebanyak 1.

Langkah 6− Di luar gelung, mula merentasi tatasusunan yang dikemas kini, keluarkan jumlah semua elemen tatasusunan dan simpannya dalam pembolehubah maxSum.

Langkah 7 − Kembalikan maxSum pada penghujung fungsi.

Contoh

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int q, int x[], int y[]) {
    int maxSum = 0;
    // Traverse X[] and Y[] array
    for (int p = 0; p < q; p++) {
        // Replacing x[p] number of elements of nums[] array with y[p] if they are lesser than y[p]
        int temp = x[p];
        sort(nums, nums + n);
        for (int q = 0; q < n; q++) {
            if (temp > 0 && nums[q] < y[p]) {
                nums[q] = y[p];
                temp--;
            }
        }
    }
    // Sum of the array
    for (int p = 0; p < n; p++) {
        maxSum += nums[p];
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

Output

The maximum sum we can get by replacing the array values is 708

Kerumitan masa− O(M*NlogN), di mana O(M) digunakan untuk merentasi semua pertanyaan dan O(NlogN) digunakan untuk mengisih tatasusunan.

Kerumitan Angkasa− Untuk mengisih tatasusunan, kerumitan ruang ialah O(N).

Kaedah 2

Dalam kaedah ini, kami akan menggunakan baris gilir keutamaan untuk menyimpan pasangan elemen tatasusunan dan kiraan kejadiannya.

Sebagai contoh, kami akan menolak pasangan {nums[p],1} ke dalam baris gilir keutamaan untuk setiap elemen tatasusunan. Pada masa yang sama, kami menolak pasangan {y[p], x[p]} ke dalam baris gilir keutamaan. Dalam baris gilir keutamaan, pasangan akan diisih berdasarkan elemen pertama. Oleh itu, kita boleh mengambil elemen N teratas daripada baris gilir. Di sini, untuk pasangan {y[p],x[p]}, kita boleh mengeluarkan unsur y[p] x[p] kali, dan kita perlu mengeluarkan sejumlah N elemen untuk memaksimumkan jumlahnya.

Algoritma

Langkah 1 − Mulakan 'maxSum' dengan 0 dan baris gilir keutamaan untuk menyimpan pasangan elemen dan bilangan kejadiannya.

Langkah 2− Untuk semua elemen tatasusunan, masukkan {nums[p], 1} pasangan ke dalam baris gilir.

Langkah 3 − Kemudian, masukkan pasangan {y[p], x[p]} ke dalam baris gilir keutamaan.

Langkah 4− Ulang sehingga n lebih besar daripada 0.

Langkah 4.1 − Alih keluar elemen pertama daripada baris gilir keutamaan.

Langkah 4.2 − Tambahkan first_ele * max(n, second_ele) kepada jumlah. Di sini, kami menggunakan max(n, second_ele) untuk mengendalikan kes terakhir.

Langkah 4.3 − Tolak second_ele daripada n.

Langkah 5− Kembalikan jumlah maksimum.

Contoh

#include <bits/stdc++.h>
using namespace std;

int getMaxSum(int nums[], int n, int m, int x[], int y[]) {
    int maxSum = 0, p;
    // To get maximum sum
    priority_queue<pair<int, int>> p_que;
    // Insert nums[] array pairs into the queue
    for (p = 0; p < n; p++)
        p_que.push({nums[p], 1});
    // Push replacement pairs
    for (p = 0; p < m; p++)
        p_que.push({y[p], x[p]});
    // Add the first N elements of the priority queue in the sum
    while (n > 0) {
        // Get top element of priority queue
        auto temp = p_que.top();
        // Remove top element
        p_que.pop();
        // Add value to the sum
        maxSum += temp.first * min(n, temp.second);
        // Change N
        n -= temp.second;
    }
    return maxSum;
}
int main() {
    int nums[] = {10, 8, 7, 60, 20, 18, 30, 60};
    int n = (sizeof nums) / (sizeof nums[0]);
    int m = 3;
    int x[] = {1, 2, 5};
    int y[] = {500, 10, 2};
    cout << "The maximum sum we can get by replacing the array values is " << getMaxSum(nums, n, m, x, y);
    return 0;
}

Output

The maximum sum we can get by replacing the array values is 708

Kerumitan masa - O(N*logN + m*logm), di mana O(N) dan O(m) digunakan untuk melintasi tatasusunan yang diberikan dan O(logN) digunakan untuk memasukkan dan memadam elemen dalam baris gilir.

Kerumitan ruang - O(N+M) untuk menyimpan pasangan dalam baris gilir.

Dalam kaedah pertama, kita perlu mengisih tatasusunan dalam setiap lelaran untuk mencari unsur x[p] terkecil. Gunakan baris gilir keutamaan untuk mengisih elemen secara automatik semasa ia dimasukkan atau dialih keluar kerana ia menggunakan struktur data timbunan. Oleh itu, ia meningkatkan prestasi kod anda.

Atas ialah kandungan terperinci Jumlah maksimum tatasusunan yang mungkin selepas melakukan operasi yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!