[Mảng 1 Chiều Cơ Bản]. Bài 58. Cặp đôi xa cách

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

28Tech

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng A[] gồm N phần tử bạn hãy tìm 2 số A[i] và A[j] trong mảng với A[i] = A[j] và i < j sao cho j - i đạt giá trị lớn nhất.

Ví dụ : A = [1, 2, 3, 1, 1, 5] thì cặp i = 0 và j = 4 là kết quả tốt nhất.

Bạn hãy tìm giá trị lớn nhất của j - i, nếu trong mảng không tồn tại cặp A[i] và A[j] (i < j) bằng nhau thì bạn hãy in ra 28tech.

Đầu vào

Dòng 1 là N : số phần tử trong mảng

Dòng 2 là N số viết cách nhau 1 dấu cách

Giới hạn

1≤N≤10^3

0≤A[i] ≤10^6

Đầu ra

In ra đáp án của bài toán

Ví dụ :

Input 01

6
1 2 3 1 1 5

Output 01

Input 02

5
1 2 3 4 5

Output 02

28tech

Bình luận

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

-1

anhthuy_ đã bình luận lúc 26, Tháng 11, 2025, 9:02

full ac cho sigma

#include <bits/stdc++.h>
#define iosf ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define fi first
#define se second
using namespace std;
template &lt;typename T,typename P> using pa = pair<T,P>;

int main(){
    iosf

    int n;

    cin >> n;

    map<int,pa<int,int>> mp;
    int index = 1;

    while(n--){
        int num; cin >> num;

        if (mp.count(num) != 1){
            mp[num] = {index,index};
        } else {
            mp[num].fi = min(mp[num].fi,index);
            mp[num].se = max(mp[num].se,index);
        }

        index++;
    }

    int MAX = -1;
    bool none = true;

    for(auto [num,index] : mp){
        if (index.fi == index.se) continue;

        none = false;

        int farthest = index.second;
        int nearest = index.first;

        MAX = max(MAX,farthest-nearest);
    }

    if (none) {
        cout << "28tech";
    } else {
        cout << MAX;
    }

    return 0;
}