Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n và một số S. Nhiệm vụ của chúng ta là Tìm giá trị lớn nhất có thể của giá trị nhỏ nhất của mảng đã sửa đổi .
Đây là các quy tắc để sửa đổi mảng,
-
Sự khác biệt giữa tổng các phần tử mảng trước và sau khi sửa đổi phải là S.
-
Giá trị âm trong mảng đã sửa đổi không được phép.
-
Nếu mảng được sửa đổi, các giá trị nhỏ nhất của mảng cần phải được tối đa hóa.
-
Việc sửa đổi mảng có thể được thực hiện bằng cách tăng hoặc giảm bất kỳ phần tử nào của mảng .
Sử dụng các ràng buộc này, chúng ta cần tìm mảng mới và trả về giá trị lớn nhất cho phần tử nhỏ nhất của mảng.
Hãy lấy một ví dụ để hiểu vấn đề,
Input : arr[] = {4, 5, 6} S = 2
Output : 4 Giải thích
mảng đã sửa đổi là {4, 5, 5}
Phương pháp tiếp cận giải pháp
Chúng ta cần tối đa hóa giá trị nhỏ nhất của mảng đã sửa đổi. Chúng tôi sẽ thực hiện việc này bằng cách sử dụng tìm kiếm nhị phân của giá trị tối ưu cho giá trị nhỏ nhất nằm giữa 0 (nhỏ nhất có thể) và arr min (lớn nhất có thể). Chúng tôi sẽ kiểm tra sự khác biệt để có giá trị nhỏ nhất có thể.
Một số điều kiện đặc biệt,
Nếu S lớn hơn tổng mảng, thì không thể có giải pháp nào.
Nếu S bằng tổng mảng thì 0 sẽ là giá trị của phần tử nhỏ nhất.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The maximum value of minimum element of the modified array is 4