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

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

배열 수정 규칙은 다음과 같습니다.

• 수정 전과 수정 후의 배열 요소의 합은 S가 되어야 합니다.

• 수정된 배열에는 음수 값이 허용되지 않습니다.

• 수정된 배열이 배열의 최소값을 최대화해야 하는 경우.

• 배열의 요소를 더하거나 빼서 배열을 수정할 수 있습니다.

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

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

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

Explanation

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

Solution

수정된 배열의 최소값을 최대화해야 합니다. 이진 검색을 사용하여 0(가능한 가장 작은 값) 과 arr_min(가능한 가장 큰 값) 사이의 최소값에 대한 최상의 값을 찾습니다. 가능한 가장 작은 값을 얻기 위해 차이를 확인하겠습니다.

일부 특수 조건,

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

Output

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

위 내용은 C++에서 수정된 배열의 최소값 중 가능한 최대값 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!