C++のk個の更新で等しくすることができる最大要素

与えられたタスクは、要素を最大k回インクリメントした後、特定の配列で等しくすることができる要素の最大数を見つけることです。

例を使用して、私たちがしなければならないことを理解しましょう-

入力

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

出力

2

説明

ここでは、1を3回インクリメントし、3を4回インクリメントすることで、2つの4を取得できます。これにより、a [] ={4、4、8}

入力

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

出力

0

以下のプログラムで使用されるアプローチは次のとおりです

• main（）関数で、int a []、sizeを初期化します。 およびk 配列要素、配列のサイズ、および可能な最大更新をそれぞれ格納します。

• max（）関数では、最初に配列を昇順で並べ替えてから、さらに2つの配列を宣言します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

• ループの後、int Lt =1、Rt =size、結果を初期化して、それぞれ左の値、右の値、および最終的な答えを格納します。その後、二分探索を開始します。

• 条件（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;
}

出力

2