Sum of Mutated Array Closest to Target หาค่า mutate ให้ผลรวมใกล้ target ใน C++

ให้อาร์เรย์ arr และ target หาค่า value ที่เมื่อเปลี่ยนทุกตัวที่ > value ให้ = value ผลรวมจะใกล้ target มากที่สุด (ถ้าเท่ากัน ให้ค่าน้อยสุด)

ตัวอย่าง: [4,9,3], target=10 → 3 (array กลายเป็น [3,3,3] sum=9)

วิธีแก้ปัญหา (Mathematical Derivation)

1. avg = target / n
2. sum = ผลรวมตัวที่ ≤ avg, cnt = จำนวนตัวที่ ≤ avg
3. ถ้า target - sum = 0 → คืน avg
4. high = ceil((target - sum) / (n - cnt))
5. low = floor((target - sum) / (n - cnt))
6. เปรียบเทียบ lowDiff และ highDiff คืนค่าที่ใกล้กว่า (ถ้าเท่ากันให้ 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, 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));
        return (lowDiff <= highDiff) ? low : high;
    }
};

int main() {
    vector<int> v = {4,9,3,2};
    Solution ob;
    cout << ob.findBestValue(v, 10);
    return 0;
}

Input

[4,9,3,2] 10

Output

3