C++でターゲットに最も近い変異配列の合計を求める方法

整数配列 arr と目標値 target が与えられたとします。この問題では、配列内の value より大きいすべての要素を value に置き換えたとき、その配列の合計が目標値にできるだけ近くなるような整数 value を見つけます。合計が等しくなる候補が複数存在する場合は、より小さい方の整数を返します。

例として、配列が [4,9,3]、目標値が 10 の場合を考えてみましょう。value を 3 とすると、配列は [3,3,3] となり、合計は 9 になります。これは 10 に最も近いため、答えは 3 となります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• n := 配列のサイズ、avg := total / n、sum := 0、cnt := 0 と初期化します
• i を 0 から n − 1 の範囲でループします
  • arr[i] ≤ avg の場合、sum := sum + arr[i] とし、cnt を 1 増やします
• target − sum = 0 の場合、avg を返します
• high := (target − sum) / (n − cnt) の切り上げ値
• low := (target − sum) / (n − cnt) の切り下げ値
• lowDiff := |target − (low × (n − cnt) + sum)|
• highDiff := |target − (high × (n − cnt) + sum)|
• lowDiff ≤ highDiff の場合、low を返します
• そうでなければ high を返します

コードの考え方

まず、avg(目標値を要素数で割った平均)以下の要素は、どのような value を選んでも影響を受けないため、あらかじめ合計 sum に加算し、その個数を cnt として数えておきます。残りの n − cnt 個の要素はすべて value 以上であるため、これらを value に置き換えたときの合計は「value × (n − cnt) + sum」と表せます。この合計が target に最も近くなるように、(target − sum) / (n − cnt) の切り上げ・切り下げの2つの候補を比較し、差が小さい方を採用します。差が同じ場合は、条件に従って小さい方の low を返します。

以下の実装例を見ると、理解がさらに深まるでしょう。

実装例(C++)

#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