Tổng mảng biến đổi gần mục tiêu nhất (Sum of Mutated Array Closest to Target) trong C++

Cho mảng arr và target. Tìm giá trị value sao cho khi thay mọi phần tử > value bằng value, tổng mảng mới gần target nhất. Nếu bằng nhau chọn value nhỏ nhất.

Ví dụ: arr=[4,9,3], target=10 → value=3 (mảng [3,3,3] tổng 9).

Thuật toán (Tính toán trực tiếp)

1. avg = target / n.
2. Tính tổng các phần tử ≤ avg (gọi sum), đếm cnt.
3. Phần tử còn lại n-cnt sẽ được đặt = value. Giải value ≈ (target-sum)/(n-cnt).
4. Thử floor và ceil, chọn giá trị cho độ chênh lệch nhỏ nhất.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findBestValue(vector& arr, int target) {
        int n = arr.size();
        int avg = target / n;
        int sum = 0, cnt = 0;
        for (int x : arr) if (x <= avg) { sum += x; cnt++; }
        if (target == sum) return avg;
        int high = ceil((target - sum) * 1.0 / (n - cnt));
        int low = floor((target - sum) * 1.0 / (n - cnt));
        int lowDiff = abs(target - (low*(n-cnt) + sum));
        int highDiff = abs(target - (high*(n-cnt) + sum));
        return lowDiff <= highDiff ? low : high;
    }
};

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

Đầu vào / Đầu ra

Input: [4,9,3,2] 10

Output: 3