मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है जिसे अंक और एक पूर्णांक k कहा जाता है, जो कि थ्रेशोल्ड मान है, हम एक सकारात्मक पूर्णांक भाजक का चयन करेंगे और सभी सरणी को इसके द्वारा विभाजित करेंगे और विभाजन के परिणाम का योग करेंगे। हमें सबसे छोटा भाजक इस प्रकार ज्ञात करना है कि ऊपर उल्लिखित परिणाम थ्रेशोल्ड मान k से कम या उसके बराबर हो। उदाहरण के लिए - यदि अंक =[1,2,5,9] और के =6, तो आउटपुट 5 होगा। हम योग को (1+2+5+9) =17 के रूप में प्राप्त कर सकते हैं जब भाजक 1 है। यदि भाजक 4 है, तो हम योग 7 प्राप्त कर सकते हैं (1+1+2+3), जब भाजक 5 है, तो योग होगा (1+1+1+2) =5
यह गारंटी है कि एक उत्तर होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- चेक नामक एक विधि को परिभाषित करें, इसमें x, सरणी संख्या और k जैसे तीन पैरामीटर होंगे, यह इस प्रकार होगा -
- योग :=0
- मैं के लिए 0 से लेकर अंकों के आकार तक - 1
- योग :=योग + अंकों का अधिकतम मूल्य [i] / x
- सही लौटें, अगर योग <=k, अन्यथा गलत
- वास्तविक विधि नीचे की तरह होगी -
- निम्न सेट करें:=1 और उच्च:=inf
- जबकि कम <उच्च
- मध्य :=निम्न + (उच्च-निम्न)/2
- यदि चेक (मध्य, अंक, के), तो उच्च:=मध्य, अन्यथा निम्न:=मध्य + 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