ปัญหา
สมมติว่าเรามีอาร์เรย์ที่มี n จำนวนเต็ม เราต้องหาเซิร์บอาร์เรย์ที่ติดกันซึ่งมีความยาวมากกว่าหรือเท่ากับ k ที่มีค่าเฉลี่ยสูงสุด เราต้องหาค่าเฉลี่ยสูงสุดนั้น
เช่น ถ้าผนวกเข้าเป็น [1,12,-5,-6,50,3], k = 4 ผลลัพธ์จะเป็น 12.75 เนื่องจากเมื่อความยาวเป็น 5 ค่าเฉลี่ยสูงสุดคือ 10.8 เมื่อความยาวเป็น 6 ค่าเฉลี่ยสูงสุดคือ 9.16667 ดังนั้นผลลัพธ์คือ 12.75
วิธีแก้ปัญหา
- กำหนดฟังก์ชัน ok() รับ x, อาร์เรย์ nums, k
- n := ขนาดของ nums
- กำหนดอาร์เรย์ arr ขนาด n
- for i := 0 ถึง n-1 ทำ: arr[i] := nums[i] - x
- sum := 0, last := 0
- for i := 0 ถึง k-1 ทำ: sum := sum + arr[i]
- ถ้า sum >= 0 คืนค่า true
- for i := 0, j := k; j < n; i++, j++ ทำ:
- last := last + arr[i]
- sum := sum + arr[j]
- ถ้า last < 0 แล้ว: sum := sum - last; last := 0
- ถ้า sum >= 0 คืนค่า true
- คืนค่า false
- จากเมธอดหลัก:
- ret := 0, low := -inf, high := inf
- while high - low > 10^-5 ทำ:
- mid := low + (high - low) / 2
- ถ้า ok(mid, nums, k) เป็น true แล้ว: low := mid; ret := mid
- มิฉะนั้น: high := mid
- คืนค่า ret
ตัวอย่างโค้ด C++
#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;
}
};
int 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
