[C10_HN_KHTN_24] Khoảng cách nhỏ nhất
Xem dạng PDF
Gửi bài giải
Đ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
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, Python
Cho một dãy ~N~ số nguyên ~a_0, a_1, \ldots, a_{N-1}~. Khoảng cách giữa hai số ~a_i~ và ~a_j~ ~(0 \le i, j \le N - 1; i \ne j)~ được định nghĩa là ~|i - j|~. Tìm khoảng cách nhỏ nhất giữa hai số bằng nhau trong dãy, nếu không có hai số nào bằng nhau, in ra ~-1~.
Yêu cầu
Tìm khoảng cách nhỏ nhất giữa hai số bằng nhau trong dãy.
Dữ liệu đầu vào
Gồm hai dòng:
- Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 10^5)~.
- Dòng thứ hai chứa ~N~ số nguyên ~a_0, a_1, \ldots, a_{N-1}~ ~(-10^9 \le a_i \le 10^9)~.
Dữ liệu đầu ra
Gồm một số nguyên duy nhất là kết quả của bài toán.
Ràng buộc dữ liệu
- 80% số test có ~N \le 10^3~ và ~-10^5 \le a_i \le 10^5~ với ~0 \le i \le N-1~.
- 20% số test còn lại không có ràng buộc gì thêm.
Ví dụ
Ví dụ 1
INPUT
5
7 2 3 2 7
OUTPUT
2
Giải thích: Dãy ~7, 2, 3, 2, 7~ có hai cặp số bằng nhau:
- ~7~ ở vị trí ~0~ và ~4~, khoảng cách ~4~;
- ~2~ ở vị trí ~1~ và ~3~, khoảng cách ~2~;
Nên kết quả của bài toán là ~2~.
Bình luận
include <bits/stdc++.h>
using namespace std;
define ll long long
define fi first
define se second
int a[100005],n,ans=1e9; mapm;
int main()
{
cin>>n;
for( int i=1; i<=n; ++i)
{
cin>>a[i];
m[a[i]].push_back(i);
}
for (auto &p:m)
{
if( p.se.size()>=2)
{
for( int i=0; i<p.se.size()-1; ++i)
{
ans=min(ans,abs(p.se[i+1]-p.se[i]));
}
}
}
if( ans==1e9) cout<<-1;
else cout<<ans;
}