Hướng dẫn giải của [200 đề thầy Đức] Bài 173: Dãy con có giá trị trung bình lớn nhất


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.

Hướng dẫn giải

Tìm đoạn con liên tiếp có giá trị trung bình lớn nhất; nếu có nhiều đoạn như vậy thì lấy đoạn dài nhất và in độ dài của nó.

Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 2000~

Thử mọi đoạn ~[L, R]~, tính tổng rồi so sánh trung bình bằng cách nhân chéo: ~s_1 \cdot len_2 > s_2 \cdot len_1~. Tổng có thể tới ~10^{14}~ nhân với độ dài tới ~10^5~ nên dùng __int128 để tránh tràn. Nếu chỉ nộp sub này: đúng 21/31 test.

Sub 2: Đoạn toàn số lớn nhất — ~O(n)~

Trung bình của một đoạn không bao giờ vượt phần tử lớn nhất ~M~, và chỉ bằng ~M~ khi mọi phần tử của đoạn đều bằng ~M~. Vì vậy đáp án là độ dài dãy liên tiếp dài nhất gồm các số bằng ~M~. Bẫy: nếu mọi số đều bằng 0 thì ~M = 0~ và đáp án là ~N~. Nếu chỉ nộp sub này: đúng 31/31 test.

Chương trình hoàn chỉnh

main đọc ~N~ và dãy. Nếu ~N \le 2000~ thì gọi sub1, ngược lại gọi sub2.

#include <bits/stdc++.h>
using namespace std;

int n;
long long a[100005];

// Sub 1: vét cạn O(n^2). Thử mọi đoạn [L, R], so sánh trung bình bằng phép nhân chéo.
// Dùng __int128 vì tổng đoạn tới 10^14 nhân độ dài tới 10^5 có thể tràn long long.
void sub1() {
    bool have = false;
    long long bs = 0;   // tổng đoạn tốt nhất
    int bl = 0;         // độ dài đoạn tốt nhất
    for (int L = 1; L <= n; L++) {
        long long s = 0;
        for (int R = L; R <= n; R++) {
            s += a[R];
            int len = R - L + 1;
            bool better;
            if (!have) better = true;
            else {
                __int128 lhs = (__int128)s * bl, rhs = (__int128)bs * len;
                better = lhs > rhs || (lhs == rhs && len > bl);
            }
            if (better) {
                have = true;
                bs = s;
                bl = len;
            }
        }
    }
    printf("%d\n", bl);
}

// Sub 2: O(n). Trung bình của đoạn không bao giờ vượt phần tử lớn nhất M,
// và bằng M chỉ khi mọi phần tử của đoạn đều bằng M. Nên đáp án là dãy liên tiếp dài nhất gồm các số M.
void sub2() {
    long long M = a[1];
    for (int i = 2; i <= n; i++) M = max(M, a[i]);
    int best = 0, cur = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == M) cur++;
        else cur = 0;
        best = max(best, cur);
    }
    printf("%d\n", best);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n <= 2000) sub1();   // dữ liệu nhỏ: vét cạn
    else sub2();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.