C++에서 k 업데이트와 동일하게 만들 수 있는 최대 요소

<시간/>

주어진 작업은 최대 k 번 요소를 증가시킨 후 주어진 배열에서 동일하게 만들 수 있는 요소의 최대 수를 찾는 것입니다.

이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -

입력

a[] = {1, 3, 8}, k = 4

출력

설명

여기서 우리는 1을 3번 증가시키고 3을 4번 증가시켜 두 개의 4를 얻을 수 있습니다. 그러면 a[] ={4, 4, 8}

입력

arr = {2, 5, 9}, k = 2

출력

아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

main() 함수에서 int a[], 크기 초기화 및 k 배열 요소, 배열 크기 및 가능한 최대 업데이트를 각각 저장합니다.
max() 함수에서 먼저 배열을 오름차순으로 정렬한 다음 두 개의 배열을 더 선언합니다. int p[size + 1] 및 m[크기 + 1] 접두사 합계와 최대값을 각각 저장합니다.
i =0에서 i<=크기까지 루프하고 p[i] =0 및 m[i] =0을 초기화합니다.
루프 외부에 m[0] =arr[0] 및 p[0] =arr[0]을 넣습니다.
i =1에서 i<크기까지 루프하고 p[i] =p[i - 1] + arr[i]를 입력하여 접두사 합계를 계산하고 m[i] =max(m[i - 1], arr[i]를 입력합니다. ) 해당 위치까지의 최대값을 계산합니다.
루프 후 int Lt =1, Rt =크기, 결과를 각각 왼쪽 값, 오른쪽 값 및 최종 답을 저장할 결과를 초기화합니다. 그런 다음 바이너리 검색을 시작합니다.
조건(Lt
그렇지 않으면 간단히 Rt =mid -1을 입력하십시오.
루프 출력 결과 외부.
bool EleCal() 함수에서 (int i =0, j =x; j <=size;j++, i++)
조건으로 for 루프를 시작합니다.
루프 내에서 (x * m[j] - (p[j] - p[i]) <=k)인지 확인합니다. 그렇다면 true를 반환합니다. 루프 밖에서는 false를 반환합니다.

예

#include <bits/stdc++.h>
using namespace std;
bool EleCal(int p[], int m[], int x, int k, int size){
   for (int i = 0, j = x; j <= size; j++, i++){
      if (x * m[j] - (p[j] - p[i]) <= k)
         return true;
   }
   return false;
}
void Max(int arr[], int size, int k){
   // sorting array in ascending order
   sort(arr, arr + size);
   int p[size + 1];
   //array for maximum value
   int m[size + 1];
   // Initialize prefix array and maximum array
   for (int i = 0; i <= size; ++i){
      p[i] = 0;
      m[i] = 0;
   }
   m[0] = arr[0];
   p[0] = arr[0];
   for (int i = 1; i < size; i++){
      // Calculating prefix sum of the array
      p[i] = p[i - 1] + arr[i];
      // Calculating max value upto that position
      // in the array
      m[i] = max(m[i - 1], arr[i]);
   }
   // Binary seach
   int Lt = 1, Rt = size, result;
   while (Lt < Rt){
      int mid = (Lt + Rt) / 2;
      if (EleCal(p, m, mid - 1, k, size)){
         result = mid;
         Lt = mid + 1;
      }
      else
         Rt = mid - 1;
   }
   //answer
   cout<<result;
}
// main function
int main(){
   int a[] = { 1, 3, 8 };
   int size = sizeof(a) / sizeof(a[0]);
   int k = 4;
   Max(a, size, k);
   return 0;
}