C++でターゲットに最も近い変異配列の合計

整数配列arrとターゲット値targetがあるとすると、指定された配列のvalueより大きいすべての整数を変更すると、配列の合計が次のように等しくなるような整数値を見つける必要があります。ターゲットにすることが可能です。それらが同じである場合は、そのような最小の整数を返します。したがって、配列が[4,9,3]のようで、ターゲットが10の場合、出力は3を使用すると3になり、配列は[3,3,3]になるため、合計は9になります。これは最も近い要素です。 10まで。

これを解決するには、次の手順に従います-

• n：=配列のサイズ、avg：=total / n、set sum：=0およびcnt：=0
• 0からn–1の範囲のiの場合
  • arr [i] <=avgの場合、sum：=sum + arr [i]、cntを1増やします
• target – sum =0の場合、平均を返します
• 高：=（ターゲット-合計）/（n-cnt）の上限
• 低：=（ターゲット-合計）/（n-cnt）のフロア
• lowDiff：=| target –（low *（n --cnt）+ sum）|
• highDiff：=| target –（high *（n --cnt）+ sum）|
• lowDiff <=highDiffの場合、lowを返します
• ハイに戻ります。

理解を深めるために、次の実装を見てみましょう-

例

#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