CSES - Playlist | Danh sách phát

View as PDF

All submissions

Best submissions

Authors:

Flower_On_Stone , HoaiAnDeepTry , nguyendangquocthinh

Problem types

Points: 1200 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

You are given a playlist of a radio station since its establishment. The playlist has a total of \(n\) songs.

What is the longest sequence of successive songs where each song is unique?

Input

The first input line contains an integer \(n\): the number of songs.
The next line has \(n\) integers \(k_1,k_2,\ldots,k_n\): the id number of each song.

Output

Print the length of the longest sequence of unique songs.

Constraints

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

Example

Sample input

8  
1 2 1 3 2 7 4 2

Sample output

Comments

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;
}

Hint

// Code này rùa, ai giải thích giúp với !!!!

include<bits/stdc++.h>

using namespace std;

ll a[200005];

int main()
{

ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);

int n; cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];

unordered_map <ll, int> mp;
unordered_map <ll,int> vt;
int ans=0,cnt=0;
for (int i=1;i<=n;i++){
  mp[a[i]]++;
  cnt++;
  if (i-vt[a[i]]<cnt && mp[a[i]]>0 )  { cnt=i-vt[a[i]]; mp[a[i]]--; }
  ans=max(ans,cnt);
  vt[a[i]]=i;
}

cout<<ans;

}

hien18086 • 12:14 a.m. 29 jan, 2024 •

https://ideone.com/nwbAJC
cho em hỏi code này tại sao lại sai 3 test ạ

1
Reply Share

1 reply

tk22NguyenHuuHongQuan • 6:24 p.m. 4 dec, 2022 •

In độ dài của dãy dài nhất mà mỗi bài hát là duy nhất là sao vậy mình vẫn chưa hiểu lắm

8
Reply Share

1 reply