minict12
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
1023M
Input:
bàn phím
Output:
màn hình
Cho mảng \(A\) gồm \(n\) số nguyên. Một đoạn con liên tục của mảng \(A\) là một hoặc nhiều phần từ liên tục lấy tử mảng \(A\). Một đoạn con liên tục được gọi là hoàn hảo nếu như nó chứa không nhiều hơn \(k\) số nguyên khác nhau.
Yêu cầu
- Hãy tìm đoạn con liên tục hoàn hảo dài nhất của mảng \(A\).
Input
- Dòng đầu tiên là hai số nguyên dương \(n\), \(k\) (\(1 \leq k \leq n \leq 5*10^5\)).
- Dòng thứ hai là một dãy số nguyên \(A_1, A_2, ..., A_n\) (\(0 \leq A_i \leq 10^6\)).
Output
- In ra hai số nguyên \(l, r\) (\(1 \leq l \leq r \leq n\)) - chỉ số bắt đầu và chỉ số kết thúc của đoạn con liên tục hoàn hảo dài nhất. Nếu như có nhiều đoạn con dài nhất, in ra đoạn con có chỉ số \(l\) nhỏ nhất.
Scoring
- Subtask \(1\) (\(50\%\) số điểm): \(n \le 100\).
- Subtask \(2\) (\(50\%\) số điểm): không có điều kiện gì thêm
Example
Test 1
Input
3 2
1 2 3Output
1 2
Bình luận
Mình sẽ chia sẻ cách sử dụng thao tác 2 con trỏ + đếm phân phối của mình nhé:
Gọi res là số phần tử khác nhau của dãy đang xét,l là độ dài lớn nhất của dãy hoàn hảo tìm đc. i=1 và j=2. Nếu ai != aj gán res=2 ngược lại res=1.
Ta sử dụng 1 mảng m để đếm số lần xuất hiện của phần tử.
trong khi j<=n ta sẽ xét 2 th:
3.1
Nếu res<=k: kiểm tra xem độ dài dãy hiện tại có lớn hơn l hay không. Nếu có ta gán 2 biến head=i và tail =j;
Gán j++ và kt xem m[aj]==1 hay không (tức là aj có phải là phần tử mới xuất hiện hay không) nếu có thì res++;
3.2
Nếu res>k: ta giảm m[ai] 1 đơn vị (loại pt ở vị trí i). Sử dụng vòng while kt nếu m[ai]!=0 (tức là vẫn tồn tại ak=ai (i<k<=j) thì i++ và m[ai]--
Gán i++ (bù cho m[ai] ta giảm ban đầu) và res-- (ta loại 1 phần tử riêng biệt ra khỏi dãy)
??
n2baontbẩn thế
n2baont bẩn thế