Đường đi đẹp nhất

[Crazy_Things]

Cho em hỏi sao cách làm của em ko AC v ạ
5/10 test

Tóm tắt đề:
Cho mảng A, tìm đoạn con liên tiếp dài nhất có trung bình cộng = k

• in ra vị trí bắt đầu của đoạn con (nếu có nhiều đoạn con thì in ra vị trí nhỏ nhất)
• in ra số lượng phần tử của đoạn con

Idea làm bài này của em là
Trừ đi các phần tử trong mảng 1 lượng là K
Thì em nghĩ bài toán lúc này sẽ là tìm đoạn con có tổng = 0 dài nhất
Em sử dụng prefixSum và map để tìm ra đoạn con có tổng = 0 dài nhất

Đây là code của em ạ:

void solve() {
        int n, k;
        cin >> n >> k;
        vector<int> a(n);
        unordered_map<int, int> b;

        int prefixSum = 0, start = n + 1, max_length = 0;
        for (int i = 0; i < n; ++i) {
                cin >> a[i];
                a[i] -= k;
                prefixSum += a[i];

                if (prefixSum == 0) {
                        start = 1;
                        max_length = max(max_length, i + 1);
                }
                else if (b.count(prefixSum) && i - b[prefixSum] >= max_length) {
                        start = min(start, b[prefixSum] + 2);
                        max_length = i - b[prefixSum];
                } else {
                        b[prefixSum] = i;
                }
        }
        if (max_length > 0)
                cout << start << '\n' << max_length << '\n';
        else
                cout << 0 << '\n';
}

[kisuluoibieng (Tên Gì Cũng Được)]

bạn không giải thích code thì ai biết bạn muốn làm gì
ít nhất cũng phải giải thích các biến có ý nghĩa gì, các dòng lệnh thực hiện thap tác gì?

bài này n = 100 thì chạy trâu O(n^3) bằng cách pick các cặp i/j (n^2) rồi tính tổng (n) để thử
cũng đã có thể pass được 50% testcase rồi
chỉ có thể là bạn làm sai mà thôi

bằng một cách nào đó cũng có tên gọi giống giống “prefix sum” mà khâu tính tổng với từng cặp đó có thể biến từ O(n) thành O(1), như vậy cuối cùng sẽ chỉ là O(n^2)
còn code của bạn không có giải thích gì nên mình cũng không muốn suy nghĩ nhiều, không ý kiến

[Crazy_Things]

Em thấy rằng
(a[i] + a[i + 1] + … + a[i + n]) / n = k
-> (a[i] - k) + (a[i + 1] - k) + … + (a[i + n] - k) = 0

Nên thay vì tính trung bình cộng các đoạn con thì em xoá từng phần tử 1 lượng là K
Và tổng đoạn con từ a[i] đến a[j] = 0 thì tbc = k

Nên lúc này em nghĩ bài toán sẽ là tìm đoạn con có tổng = 0 dài nhất ạ

Đầu tiên là em trừ các phần tử 1 lượng là k
Rồi cộng dồn vào biến prefixSum
Tiếp theo em kiểm tra từ [0, i] nếu prefixSum = 0 (tbc = k) thì em cập nhật vị trí
start = 1 và max_length là i + 1

if (prefixSum == 0) {
      start = 1;
      max_length = max(max_length, i + 1);
}

Tiếp theo em kiểm tra trường hợp thứ 2
Đoạn con từ [pi, i] có tổng = 0
=> 2 đoạn con từ a[0] đến a[i] = prefixSum và a[0] đến a[pi - 1] = prefixSum (2 đoạn con này sẽ có giá trị bằng nhau)

Nên đoạn code tiếp theo em sẽ kiểm tra đã có tổng nào trước đó bằng với prefixSum hiện tại hay chưa, em sử dụng unordered_map

Trường hợp 1 đã có tổng = prefixSum hiện tại trước đó thì em sẽ thay đổi vị trí start và max_length (nếu số lượng phần tử >= max_length thì mới thay đổi)

else if (b.count(prefixSum) && i - b[prefixSum] >= max_length) {
             start = min(start, b[prefixSum] + 2);
             max_length = i - b[prefixSum];
} 

Trường hợp 2 nếu chưa có tổng nào = prefixSum hiện tại trước đó thì em thêm vào map với prefixSum hiện tại và vị trí i hiện tại

else {
       b[prefixSum] = i;
}

Thuật toán lúc này em nghĩ là O(n) không hiểu sao lại ko AC đc ạ

[noname00 (HK boy)]

Bạn đã có ý sử dụng unordered_map rồi nhưng lại thực hiện thuật toán quá cồng kềnh.

Nói một cách đơn giản, một đoạn là dài nhất khi với vị trí bắt đầu i thì vị trí kết thúc j sẽ là vị trí xa nhất có thể về bên phải. Do vậy ta cần tạo 1 unordered_map<int, int> furthest_index lưu vị trí xa nhất về bên phải của mỗi giá trị tổng trong prefix_sum.

int prefix_sum[...] = {0};
for (int i = 1; i <= n; i++) { // 1-index
    int x;
    cin >> x;
    prefix_sum[i] += x;
    furthest_index[prefix_sum[i]] = i;
}

Sau đó làm theo cách ngây thơ nhất, với mỗi điểm đầu i ta tìm điểm j xa nhất (nếu có):

for (int i = 1; i <= n; i++) {
    if (furthest_index.count(prefix_sum[i-1]) > 0) {
        int j = furthest_index[prefix_sum[i-1]];
        if (j >= i) {
            max_beautiful_length = max(max_beautiful_length, j - i + 1);
        }
    }
}

[noname00 (HK boy)]

Mình sửa code trên một chút, thành

prefix_sum[i] += x - k;

cho giống với ý tưởng của bạn nhé

[Crazy_Things]

Em AC rồi ạ, em cảm ơn anh rất nhiều
Em có điều chỉnh lại code một tí

void solve() {
        int n, k;
        cin >> n >> k;
        vector<int> prefix_sum(n + 1, 0);
        unordered_map<int, int> furthes_index;

        int start = n + 2, max_length = 0;
        for (int i = 1; i <= n; ++i) {
                int x;
                cin >> x;
                prefix_sum[i] = prefix_sum[i - 1] + (x - k);
                furthes_index[prefix_sum[i]] = i;
        }

        for (int i = 1; i <= n; ++i) {
                if (prefix_sum[i] == 0) {
                        start = 1;
                        max_length = i;
                }
                else if (furthes_index.count(prefix_sum[i]) > 0) {
                        int j = furthes_index[prefix_sum[i]];
                        if (j > i) {
                                if (j - i > max_length) {
                                        start = i + 1;
                                        max_length = j - i;
                                }
                                else if (j - i == max_length) {
                                        start = min(start, i + 1);
                                }
                                else if (start == 1 && j - i > max_length) {
                                        start = i + 1;
                                        max_length = j - i;
                                }
                        }
                }
        }
        if (max_length > 0)
                cout << start << '\n' <<  max_length << '\n';
        else
                cout << 0;
}