CSES - Playlist | Danh sách phát - LQDOJ: Le Quy Don Online Judge

CSES - Playlist | Danh sách phát

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

Flower_On_Stone , HoaiAnDeepTry , nguyendangquocthinh

Dạng bài

Điểm: 1200 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho biết danh sách phát của một đài phát thanh kể từ khi thành lập. Danh sách phát có tổng cộng \(n\) bài hát.

Dãy các bài hát liên tiếp dài nhất, mà mỗi bài trong đó đều độc nhất là dãy nào?

Input

Dòng đầu vào đầu tiên chứa một số nguyên \(n\): số lượng bài hát.
Dòng tiếp theo có \(n\) số nguyên \(k_1,k_2,\ldots,k_n\): mã số của mỗi bài hát.

Output

In độ dài của dãy dài nhất mà mỗi bài hát là duy nhất.

Constraints

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le k_i \le 10^9\)

Example

Sample input

8
1 2 1 3 2 7 4 2

Sample output

Bình luận

Hint

Sử dụng sliding window

\(left\) và \(right\) đại diện cho đầu và cuối của dãy con hiện tại.
Nếu bài hát tại \(right\) đã có trong \(baihatdb\), xóa bài hát tại \(left\) khỏi tập hợp và tăng \(left\).
Thêm bài hát tại \(right\) vào tập hợp.

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

int main() {
    int n;
    cin >> n;
    vector<int> baihat(n);
    for (int i = 0; i < n; i++) {
        cin >> baihat[i];
    }

    unordered_set<int> baihatdb;
    int left = 0, cd = 0;

    for (int right = 0; right < n; right++) {
        while (baihatdb.count(baihat[right])) {
            baihatdb.erase(baihat[left]);
            left++;
        }
        baihatdb.insert(baihat[right]);
        cd = max(cd, right - left + 1);
    }

    cout << cd << endl;
    return 0;
}

Phản hồi

3 bình luận nữa