C++에서 수정된 배열의 최소값의 가능한 최대값 찾기

이 문제에서는 크기가 n이고 숫자 S인 배열 arr[]이 제공됩니다. 우리의 임무는 수정된 배열의 최소값 중 가능한 최대값을 찾는 것입니다. .

다음은 배열을 수정하는 규칙입니다.

• 수정 전과 수정 후의 배열 요소 합계의 차이는 S여야 합니다.

• 수정된 배열의 음수 값은 허용되지 않습니다.

• 배열을 수정한 경우 배열의 최소값을 최대화해야 합니다.

• 배열의 수정은 배열의 요소를 늘리거나 줄이는 수행할 수 있습니다. .

이러한 제약 조건을 사용하여 새 배열을 찾고 배열의 가장 작은 요소에 대해 최대화된 값을 반환해야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

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

설명

수정된 배열은 {4, 5, 5}

솔루션 접근 방식

수정된 배열의 가장 작은 값을 최대화해야 합니다. 0(가장 작은 값) 사이의 가장 작은 값에 대한 최적 값의 이진 검색을 사용하여 이 작업을 수행합니다. 및 arr_분 (최대한). 가능한 가장 작은 값의 차이를 확인합니다.

몇 가지 특별한 조건

S가 배열 합보다 크면 솔루션이 불가능합니다.

S가 배열 합과 같으면 최소 요소의 값이 0이 됩니다.

예시

솔루션 작동을 설명하는 프로그램

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

출력

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