C ++中最接近目标的突变数组的总和

假设我们有一个整数数组arr和一个目标值target,我们必须找到该整数值,以便当我们更改所有大于给定数组中value的整数等于value时,该数组的总和与可能定位。如果它们相同,则返回最小的整数。因此,如果数组类似于[4,9,3]并且目标为10,则输出将为3(使用3),数组将为[3,3,3],所以总和为9,即最近的元素至10

为了解决这个问题,我们将遵循以下步骤-

  • n:=数组大小,avg:=总数/ n,设置sum:= 0和cnt:= 0

  • 对于i,范围为0至n – 1

    • 如果arr [i] <= avg,则求和:= sum + arr [i],并将cnt增加1

  • 如果目标–总和= 0,则返回平均值

  • 高:=(目标-总和)/(n-cnt)的上限

  • 低:=(目标-总和)/(n-cnt)的下限

  • lowDiff:= |目标–(低*(n-cnt)+总和)|

  • highDiff:= |目标–(高*(n-cnt)+总和)|

  • 如果lowDiff <= highDiff,则返回低

  • 高回报。

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>

using namespace std;

class Solution {

   public:

   int findBestValue(vector<int>& arr, int target) {

      int n = arr.size();

      int avg = target / n;

      int sum = 0;

      int cnt = 0;

      for(int i = 0; i < n; i++){

         if(arr[i] <= avg){

            sum += arr[i];

            cnt++;

         }

      }

      if(target - sum == 0)return avg;

      int high = ceil(((target - sum) * 1.0)/ ((n - cnt) * 1.0));

      int low = floor(((target - sum) * 1.0) / ((n - cnt) * 1.0));

      int lowDiff = abs(target - (low * (n - cnt) + sum));

      int highDiff = abs(target - (high * (n - cnt) + sum));

      if( lowDiff <= highDiff)return low;

      return high;

   }

};

main(){

   vector<int> v = {4,9,3,2};

   Solution ob;

   cout << (ob.findBestValue(v, 10));

}

输入值

[4,9,3,2]

10

输出结果

3

以上是 C ++中最接近目标的突变数组的总和 的全部内容, 来源链接: utcz.com/z/316954.html

回到顶部