Sirpanma oyna texnikasi
Sirpanma oyna texnikasi haqida bilib oling
Kirish
Faraz qilaylik, bizga massivi va soni berilgan. Biz o‘rtacha qiymati maksimal bo‘lgan uzunligi bo‘lgan submassivni topmoqchimiz.
Sirpanma oyna texnikasi haqida bilib oling
Faraz qilaylik, bizga massivi va soni berilgan. Biz o‘rtacha qiymati maksimal bo‘lgan uzunligi bo‘lgan submassivni topmoqchimiz.
Barcha submassivlar bir xil uzunlikda bo‘lishi kerakligi sababli, bu uzunligi bo‘lgan va yig‘indisi maksimal bo‘lgan submassivni topishga teng.
Oddiy yechim — uzunligi bo‘lgan har bir submassivni tekshirib, uning o‘rtachasini alohida hisoblash.
Bu vaqt ichida ishlaydi, chunki har bir boshlang‘ich pozitsiya uchun biz butun yig‘indini boshidan qayta hisoblaymiz.
Bundan yaxshiroq qilishimiz mumkin.
Har bir submassiv uchun yig‘indini qayta hisoblash o‘rniga, biz uzunligi bo‘lgan joriy segmentning yig‘indisini saqlab turamiz va segment bir qadam o‘ngga siljiganda uni yangilaymiz.
Biz joriy segmentni oyna deb ataymiz.
Agar biz joriy oynaning yig‘indisini allaqachon bilsak, uni bir qadam o‘ngga siljitgandan so‘ng:
Shuning uchun yangi yig‘indini doimiy vaqt ichida yangilash mumkin.
Avval, birinchi oyna ning yig‘indisini hisoblang.
So‘ng, har bir keyingi pozitsiya uchun, oynani bir qadam o‘ngga siljiting:
Boshqacha aytganda, pozitsiyada tugaydigan oynaga o‘tganda, yig‘indi quyidagicha o‘zgaradi:
Joriy oynaning o‘rtachasi shunchaki:
Quyidagicha bo‘lsin
Oynalar:
Demak, maksimal o‘rtacha submassivdan olinadi.
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;
}