मान लीजिए कि हमारे पास n पूर्णांकों के साथ एक सरणी है, हमें उस सन्निहित उप-सरणी को खोजना है जिसकी लंबाई k से अधिक या उसके बराबर है जिसका अधिकतम औसत मान है। हमें अधिकतम औसत मूल्य ज्ञात करना है।
इसलिए, यदि इनपुट [1,12,-5,-6,50,3], k =4 जैसा है, तो आउटपुट 12.75 होगा, क्योंकि जब लंबाई 5 होती है, तो अधिकतम औसत मान 10.8 होता है, जब लंबाई 6 होती है। , अधिकतम औसत मूल्य 9.16667 है। इस प्रकार आउटपुट 12.75 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन को परिभाषित करें ठीक (), यह x, एक सरणी संख्या, k,
लेगा -
n :=अंकों का आकार
-
आकार की एक सरणी गिरफ्तारी परिभाषित करें:n.
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
गिरफ्तारी [i] :=अंक [i] - x
-
-
योग :=0, अंतिम :=0
-
इनिशियलाइज़ करने के लिए मैं :=0, जब i
-
योग:=योग + गिरफ्तारी [i]
-
-
यदि योग>=0, तो -
-
सही लौटें
-
-
प्रारंभ करने के लिए i :=0, j :=k, जब j
-
अंतिम:=अंतिम + गिरफ्तारी[i]
-
योग:=योग + गिरफ्तारी [जे]
-
यदि अंतिम <0, तो -
-
योग :=योग - अंतिम
-
अंतिम:=0
-
-
यदि योग>=0, तो -
-
सही लौटें
-
-
-
झूठी वापसी
-
मुख्य विधि से निम्न कार्य करें -
-
रेट :=0, लो :=-इन्फ, हाई :=इंफ
-
जबकि उच्च-निम्न> 10^-5, करें
-
मध्य:=निम्न + (उच्च-निम्न)/2
-
यदि ठीक (मध्य, अंक, के) सत्य है, तो -
-
कम :=मध्य
-
रिट :=मध्य
-
-
अन्यथा
-
उच्च :=मध्य
-
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(double x, vector <int>& nums, int k){
int n = nums.size();
double arr[n];
for (int i = 0; i < n; i++) {
arr[i] = nums[i] - x;
}
double sum = 0;
double last = 0;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
if (sum >= 0)
return true;
for (int i = 0, j = k; j < n; i++, j++) {
last += arr[i];
sum += arr[j];
if (last < 0) {
sum -= last;
last = 0;
}
if (sum >= 0)
return true;
}
return false;
}
double findMaxAverage(vector<int>& nums, int k) {
double ret = 0;
double low = INT_MIN;
double high = INT_MAX;
while (high - low > 1e-5) {
double mid = low + (high - low) / 2;
if (ok(mid, nums, k)) {
low = mid;
ret = mid;
} else {
high = mid;
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,12,-5,-6,50,3};
cout << (ob.findMaxAverage(v, 4));
} इनपुट
{1,12,-5,-6,50,3},4 आउटपुट
12.75000
