Dãy con min max
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
977M
Input:
bàn phím
Output:
màn hình
Cho một dãy gồm \(n\) số nguyên \(A=(a_1,a_2,…,a_n)\). Ta định nghĩa: đoạn con của dãy \(A\) là một dãy các phần tử liên tiếp nhau thuộc \(A\). Hoặc có thể viết \((a_i,a_{i+1},…,a_j)\) là một đoạn con của \(A\) với \(i \leq j\). Độ dài của đoạn con được tính là số phần tử của đoạn con đó, ví dụ, đoạn con trên có độ dài là \(j-i+1\).
Yêu cầu: Tìm một đoạn con có độ dài ngắn nhất chứa cả số lớn nhất và số nhỏ nhất của dãy \(A\).
Input
- Dòng đầu chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\).
- Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,….,a_n\).
Output
- Một số duy nhất là độ dài của đoạn con tìm được thỏa mãn yêu cầu đề bài.
Example
Test 1
Input
8
1 3 6 2 8 1 3 8 Output
2
Bình luận
Gợi ý
Sau khi tìm đc min và max, ta có vector<int> vfirst,vsecond với vfirst là vị trí của max, min và vsecond là giá trị max,min. Sau đó khi duyệt mảng vsecond xét nếu vsecond[i] khác vsecond[i+1] thì ta cập nhật min khoảng cách (vì các chỉ số đã được sắp xếp nên khi vsecond[i]!=vsecond[i+1] thì 2 phần tử max, min liền kề nhau nên chỉ việc cập nhật min khoảng cách)
Code C++/C++14: https://ideone.com/vad71D
có thể tìm min,max của dãy rồi tìm vị trí của min và vị trí của max, sau đó đoạn con có độ dài ngắn nhất=abs(vtmax-vtmin)+1
mình gợi ý vậy thôi :))
vd:
8
1 3 6 2 8 1 3 8
vị trí min tìm được là 6 ( tức là 1)
vị trí max tìm được là 8 ( tức là 8)
sau đó tìm độ dài đoạn con là min(res,(8-6)+1) = 2;