Hướng dẫn giải của Velefast
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Subtask 1 (~N \le 5000~)
Đơn giản là duyệt trâu qua mọi cặp đoạn con ~[i, j]~ thỏa mãn độ dài nằm trong khoảng ~[L, R]~, sau đó lấy trung bình cộng lớn nhất.
Độ phức tạp: ~\mathcal{O}(N^2)~
Subtask 2 (~N \le 2.10^5~)
Chặt nhị phân đáp án, gọi giá trị cần kiểm tra ở mỗi bước là ~\text{guess_ans}~.
Cách kiểm tra (Hàm check):
Trừ mỗi phần tử ~A_i~ đi một lượng là ~\text{guess_ans}~. Bài toán trở thành: Tìm xem có tồn tại đoạn con nào có độ dài thuộc ~[L, R]~ mà tổng các phần tử ~\ge 0~ hay không.
Dùng mảng tổng tiền tố (Prefix Sum) ~P~ của dãy vừa trừ. Khi xét đến vị trí ~i~, ta cần tìm giá trị nhỏ nhất của ~P_k~ trong khoảng chỉ số ~k \in [i - R, i - L]~. Nếu ~P_i - \min(P_k) \ge 0~ (tức ~P_k \le P_i~), thì đáp án ~\text{guess_ans}~ thỏa mãn.
Thao tác tìm giá trị nhỏ nhất trên đoạn ~[i - R, i - L]~ có thể dùng Segment Tree hoặc RMQ (Sparse Table).
Độ phức tạp: ~\mathcal{O}(N \log^2 N)~ hoặc ~\mathcal{O}(N \log N \log(\text{RANGE}))~
Subtask 3 (~N \le 10^6~)
Vẫn dùng chặt nhị phân đáp án giống Subtask 2, nhưng thay vì dùng Segment Tree hay RMQ để tìm ~\min(P_k)~, ta nhận thấy cửa sổ ~[i - R, i - L]~ là một cửa sổ trượt khi ~i~ tăng dần.
Do đó, ta sử dụng Deque (Monotonic Deque) để duy trì giá trị nhỏ nhất của mảng prefix sum trong cửa sổ trượt này. Việc này giúp hàm check giảm từ ~\mathcal{O}(N \log N)~ xuống còn ~\mathcal{O}(N)~.
Độ phức tạp: ~\mathcal{O}(N \log(\text{RANGE}))~
#include <bits/stdc++.h> #define x0 ___x0 #define y0 ___y0 #define y1 ___y1 #define fi first #define se second #define endl '\n' #define pos pisosi #define pb push_back #define pf push_front #define div ___div #define next ___next #define prev ___prev #define left ___left #define right ___right #define pq priority_queue #define MASK(i) (1ll<<(i)) #define BIT(x, i) (((x) >> (i)) & 1) #define sz(v) (int)v.size() #define all(v) v.begin(), v.end() #define filter(v) v.resize(unique(all(v)) - v.begin()) using namespace std; template<class X, class Y> bool minimize(X &x, const Y&y){ if (x<=y) return false; else{ x = y; return true; } } template<class X, class Y> bool maximize (X &x, const Y&y){ if (x>=y) return false; else{ x = y; return true; } } typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ll, int> pli; typedef tuple<int, int, int> tp3; typedef vector<int> vi; const string name = "velefast"; ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// const int lim = 1e6, limit = lim+5; int n, A[limit], L, R; double sum[limit]; bool check (double avg){ deque <int> dq; for (int i=1; i<=n; i++){ sum[i] = sum[i-1]+A[i]-avg; if (i>=L){ while (!dq.empty() && sum[dq.back()]>=sum[i-L]){ dq.pop_back(); } dq.push_back(i-L); } while (!dq.empty() && dq.front()<i-R) dq.pop_front(); if (!dq.empty() && sum[i]>=sum[dq.front()]) return true; } return false; } void process() { cin>>n>>L>>R; for (int i=1; i<=n; i++) cin>>A[i]; double l = 1000000000, r = 0; for (int i=1; i<=n; i++){ minimize (l, A[i]); maximize (r, A[i]); } for (int i=1; i<=75; i++){ double mid = (l+r)/2; if (check(mid)){ l = mid; } else{ r = mid; } } cout<<fixed<<setprecision(9)<<l; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen((name+".inp").c_str(), "r")){ freopen ((name+".inp").c_str(), "r", stdin); freopen ((name+".out").c_str(), "w", stdout); } int testcase = 1; // cin >> testcase; for(int i = 1; i <= testcase; i++) { process(); } return 0; }