在C ++中,k次更新可以使最大元素相等

给定任务是在给定数组的元素最多增加k次之后,找到可以使相等的元素的最大数量。

现在让我们使用示例了解我们必须做的事情-

输入项

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

输出结果

2

说明

在这里,我们可以通过将1加三倍并加3四倍来获得两个四,这使得a [] = {4,4,8}

输入项

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

输出结果

0

在以下程序中使用的方法如下

  • main()函数中初始化int a [],sizek分别存储数组元素,数组大小和最大可能更新。

  • max()函数中,首先按升序对数组进行排序,然后再声明另外两个数组int p [size + 1]m [size + 1],它们将分别存储前缀和和最大值。

  • 从i = 0循环直到i <= size并初始化p [i] = 0和m [i] = 0。

  • 在循环外部放置m [0] = arr [0]和p [0] = arr [0]。

  • 从i = 1直到i <size循环,然后将p [i] = p [i-1] + arr [i]计算出前缀总和,然后将m [i] = max(m [i-1],arr [i ])计算到该位置的最大值。

  • 循环后,初始化int Lt = 1,Rt = size,结果分别存储左值,右值和最终答案。之后,启动二进制搜索。

  • 在条件(Lt <Rt)下启动while循环。在循环内部放入int mid =(Lt + Rt)/2。检查是否为(EleCal(p,m,mid-1,k,size))。如果是这样,则将结果= mid和Lt = mid +1。

  • 否则,简单地将Rt = -1中。

  • 循环外打印结果。

  • 在函数bool中EleCal()启动条件为(int i = 0,j = x; j <= size; j ++,i ++)的循环

  • 在循环内检查是否(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){
   //升序排列数组
   sort(arr, arr + size);
   int p[size + 1];
   //最大值数组
   int m[size + 1];
   //初始化前缀数组和最大数组
   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++){
      //计算数组的前缀和
      p[i] = p[i - 1] + arr[i];
      //计算到那个位置的最大值
      //在数组中
      m[i] = max(m[i - 1], arr[i]);
   }
   //二进制搜索
   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;
   }
   //答案
   cout<<result;
}
//主要功能
int main(){
   int a[] = { 1, 3, 8 };
   int size = sizeof(a) / sizeof(a[0]);
   int k = 4;
   Max(a, size, k);
   return 0;
}

输出结果

2