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
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;
-
0
vietnammuonnam_mvn
6:13 p.m. 19 Tháng 9, 2024
1 bình luận nữavậy cái đó là 8 số à hay nhỏ hơn