Cari nilai maksimum yang mungkin bagi nilai minimum tatasusunan yang diubah suai dalam C++

Dalam masalah ini, kita diberikan array arr[] saiz n dan nombor S. Tugas kita ialah mencari nilai maksimum yang mungkin daripada nilai minimum tatasusunan yang diubah suai. p>

Berikut ialah peraturan untuk mengubah suai tatasusunan,

• Jumlah elemen tatasusunan sebelum dan selepas pengubahsuaian hendaklah S.

• Tiada nilai negatif dibenarkan dalam tatasusunan yang diubah suai.

• Jika tatasusunan yang diubah suai perlu memaksimumkan nilai minimum tatasusunan.

• Suatu tatasusunan boleh diubah suai dengan menambah atau menolak mana-mana elemen tatasusunan.

Menggunakan kekangan ini, kita perlu mencari tatasusunan baharu dan mengembalikan nilai maksimum unsur terkecil dalam tatasusunan.

Mari kita ambil contoh untuk memahami masalah ini,

Input : arr[] = {4, 5, 6} S = 2
Output : 4

Penjelasan

Tatasusunan yang diubah suai ialah {4, 5, 5}

Penyelesaian

Kita perlu memaksimumkan nilai minimum tatasusunan yang diubah suai. Kami akan menggunakan carian binari untuk mencari nilai terbaik untuk minimum iaitu antara 0 (nilai terkecil yang mungkin) dan arr_min (yang terbesar mungkin). Kami akan menyemak perbezaan untuk mendapatkan nilai terkecil yang mungkin.

Sesetengah syarat khas,

Jika S lebih besar daripada jumlah tatasusunan, tiada penyelesaian yang mungkin.

Jika S sama dengan jumlah tatasusunan, 0 akan menjadi nilai elemen terkecil.

Contoh

Program yang menggambarkan cara penyelesaian kami berfungsi

#include <iostream>
using namespace std;
int findmaximisedMin(int a[], int n, int S){
   int minVal = a[0];
   int arrSum = a[0];
   for (int i = 1; i < n; i++) {
      arrSum += a[i];
      minVal = min(a[i], minVal);
   }
   if (arrSum < S)
      return -1;
   if (arrSum == S)
      return 0;
   int s = 0;
   int e = minVal;
   int ans;
   while (s <= e) {
      int mid = (s + e) / 2;
      if (arrSum - (mid * n) >= S) {
         ans = mid;
         s = mid + 1;
      }
      else
         e = mid - 1;
   }
   return ans;
}
int main(){
   int a[] = { 4, 5, 6 };
   int S = 2;
   int n = sizeof(a) / sizeof(a[0]);
   cout<<"The maximum value of minimum element of the modified array is "<<findmaximisedMin(a, n, S);
   return 0;
}

Output

The maximum value of minimum element of the modified array is 4

Atas ialah kandungan terperinci Cari nilai maksimum yang mungkin bagi nilai minimum tatasusunan yang diubah suai dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!