สมมติว่าเรามี arr อาร์เรย์จำนวนเต็มและเป้าหมายค่าเป้าหมาย เราต้องหาค่าจำนวนเต็มเพื่อให้เมื่อเราเปลี่ยนจำนวนเต็มที่มากกว่าค่าในอาร์เรย์ที่กำหนดจะเท่ากับค่า ผลรวมของอาร์เรย์จะใกล้เคียงที่สุด เป็นไปได้ที่จะกำหนดเป้าหมาย หากเหมือนกัน ให้คืนค่าจำนวนเต็มขั้นต่ำดังกล่าว ดังนั้นหากอาร์เรย์เป็นเหมือน [4,9,3] และเป้าหมายคือ 10 ดังนั้นผลลัพธ์จะเป็น 3 เช่นเดียวกับการใช้ 3 อาร์เรย์จะเป็น [3,3,3] ดังนั้นผลรวมคือ 9 ซึ่งเป็นองค์ประกอบที่ใกล้ที่สุด ถึง 10.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์ เฉลี่ย :=ยอดรวม / n ผลรวมที่ตั้งไว้ :=0 และ cnt :=0
- สำหรับ i ในช่วง 0 ถึง n – 1
- ถ้า arr[i] <=เฉลี่ย แล้ว sum :=sum + arr[i] และเพิ่ม cnt ขึ้น 1
- ถ้าเป้าหมาย – ผลรวม =0 ให้คืนค่าเฉลี่ย
- สูง :=เพดานของ (เป้าหมาย - ผลรวม) / (n - cnt)
- ต่ำ :=ชั้นของ (เป้าหมาย - ผลรวม) / (n - cnt)
- lowDiff :=|target – (low*(n - cnt) + sum)|
- highDiff :=|target – (high*(n - cnt) + sum)|
- ถ้า lowDiff <=highDiff ให้คืนค่าต่ำ
- ผลตอบแทนสูง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
