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