สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่เรียกว่า nums และจำนวนเต็ม k นั่นคือค่าขีดจำกัด เราจะเลือกตัวหารจำนวนเต็มบวกและหารอาร์เรย์ทั้งหมดตามค่านั้นแล้วรวมผลลัพธ์ของการหาร เราต้องหาตัวหารที่เล็กที่สุดเพื่อให้ผลลัพธ์ที่กล่าวถึงข้างต้นน้อยกว่าหรือเท่ากับค่าขีดจำกัด k ตัวอย่างเช่น − ถ้า nums =[1,2,5,9] และ k =6 ผลลัพธ์จะเป็น 5 เราจะได้ผลรวมเป็น (1+2+5+9) =17 เมื่อตัวหารเป็น 1 หากตัวหารเป็น 4 เราก็จะได้ผลรวม 7 เป็น (1+1+2+3) เมื่อตัวหารเป็น 5 ผลรวมจะเป็น (1+1+1+2) =5
รับรองว่าจะมีคำตอบ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดวิธีหนึ่งที่เรียกว่า ตรวจสอบ ซึ่งจะใช้พารามิเตอร์สามตัว เช่น x, array nums และ k ซึ่งจะเป็นดังนี้ −
- ผลรวม :=0
- สำหรับ i ในช่วง 0 ถึงขนาดของ nums – 1
- sum :=sum + ค่าเพดานของ nums[i] / x
- คืนค่า จริง ถ้าผลรวม <=k มิฉะนั้น เท็จ
- วิธีการจริงจะเป็นดังนี้ -
- ตั้งค่าต่ำ :=1 และสูง :=inf
- ในขณะที่ต่ำ <สูง
- กลาง :=ต่ำ + (สูง – ต่ำ)/2
- ถ้าตรวจสอบ (mid, nums, k) แล้ว high :=mid หรือ low :=mid + 1
- ผลตอบแทนสูง
- ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น −
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(int x, vector <int> &nums, int th){
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += ceil((double)nums[i]/(double)x);
}
return sum<=th;
}
int smallestDivisor(vector<int>& nums, int th) {
int low = 1;
int high = 1e7;
while(low < high){
int mid = low + (high - low)/2;
if(ok(mid, nums, th)){
high = mid;
}else low = mid + 1;
}
return high;
}
};
main(){
vector<int> v = {1,2,5,9};
Solution ob;
cout << (ob.smallestDivisor(v, 6));
} อินพุต
[1,2,5,9] 6
ผลลัพธ์
5
