Tổng số mảng đột biến gần mục tiêu nhất trong C ++

Giả sử chúng ta có một mảng số nguyên arr và một mục tiêu giá trị đích, chúng ta phải tìm giá trị nguyên sao cho khi chúng ta thay đổi tất cả các số nguyên lớn hơn giá trị trong mảng đã cho sẽ bằng giá trị, tổng của mảng gần nhất bằng có thể nhắm mục tiêu. Nếu chúng giống nhau, thì trả về số nguyên nhỏ nhất như vậy. Vì vậy, nếu mảng giống như [4,9,3] và mục tiêu là 10, thì đầu ra sẽ là 3 như sử dụng 3, mảng sẽ là [3,3,3], vì vậy tổng là 9, đó là phần tử gần nhất đến 10.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng, avg:=total / n, set sum:=0 và cnt:=0
• cho tôi trong phạm vi từ 0 đến n - 1
  • nếu arr [i] <=avg, thì sum:=sum + arr [i] và tăng cnt lên 1
• nếu target - sum =0, thì trả về giá trị trung bình
• cao:=trần của (target - sum) / (n - cnt)
• thấp:=tầng của (target - sum) / (n - cnt)
• lowDiff:=| target - (low * (n - cnt) + sum) |
• highDiff:=| target - (high * (n - cnt) + sum) |
• nếu lowDiff <=highDiff, thì trả về low
• trở lại mức cao.

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[4,9,3,2]
10

Đầu ra

3