Техникаи равзанаи лағжанда
Дар бораи техникаи равзанаи лағжанда омӯзед
Муқаддима
Фарз мекунем ба мо массиви ва адади дода шудааст. Мо мехоҳем зермаҷмӯаи пайдарпайи дарозии -ро бо қимати миёнаи максималӣ пайдо кунем.
Дар бораи техникаи равзанаи лағжанда омӯзед
Фарз мекунем ба мо массиви ва адади дода шудааст. Мо мехоҳем зермаҷмӯаи пайдарпайи дарозии -ро бо қимати миёнаи максималӣ пайдо кунем.
Азбаски ҳамаи зермаҷмӯаҳои пайдарпай бояд як дарозӣ дошта бошанд, ин ба ёфтани зермаҷмӯаи пайдарпайи дарозии бо суммаи максималӣ баробар аст.
Як ҳалли содда ин аст, ки ҳар як зермаҷмӯаи пайдарпайи дарозии -ро санҷем ва миёнаи онро мустақилона ҳисоб кунем.
Ин дар вақти кор мекунад, зеро барои ҳар як мавқеи оғоз мо тамоми суммаро аз нав ҳисоб мекунем.
Мо метавонем беҳтар кунем.
Ба ҷои аз нав ҳисоб кардани сумма барои ҳар як зермаҷмӯаи пайдарпай, мо суммаи сегменти ҷории дарозии -ро нигоҳ медорем ва ҳангоми як қадам ба рост ҳаракат кардани сегмент онро нав мекунем.
Мо сегменти ҷориро тиреза меномем.
Агар мо аллакай суммаи тирезаи ҷориро донем, пас баъд аз як қадам ба рост кӯчонидани он:
Пас суммаи навро метавон дар вақти доимӣ нав кард.
Аввал, суммаи тирезаи аввал -ро ҳисоб кунед.
Сипас, барои ҳар як мавқеи навбатӣ, тирезаро як қадам ба рост ҳаракат диҳед:
Ба ибораи дигар, ҳангоми гузаштан ба тирезае, ки дар мавқеи анҷом меёбад, сумма ба андозаи зерин тағйир меёбад:
Миёнаи тирезаи ҷорӣ танҳо чунин аст:
Бигзор
Тирезаҳо чунинанд:
Пас миёнаи максималӣ аз зермаҷмӯаи пайдарпайи ба даст меояд.
for (int i = 1; i + k - 1 <= n; i++) {
double sum = 0;
for (int j = 0; j < k; j++) {
sum += a[i + j];
}
sum /= k;
res = max(res, sum);
}
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<double> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
double sum = 0;
for (int i = 1; i <= k; i++) {
sum += a[i];
}
double res = sum / k;
for (int i = k + 1; i <= n; i++) {
sum += a[i] - a[i - k];
res = max(res, sum / k);
}
cout << fixed << setprecision(10) << res << "\n";
return 0;
}