Giá trị nhỏ nhất
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
1G
Input:
bàn phím
Output:
màn hình
Cho dãy số nguyên \(𝐴 = (𝑎_1, 𝑎_2, … , 𝑎_𝑛)\) và một số nguyên dương \(𝑘 \leq 𝑛\). Với mỗi giá trị \(𝑖\ (1 \leq 𝑖 \leq 𝑛 − 𝑘 + 1)\), hãy xác định giá trị nhỏ nhất trong \(𝑘\) phần tử liên tiếp: \(𝑎_𝑖, 𝑎_{𝑖+1}, … , 𝑎_{𝑖+𝑘−1}\)
Input
- Dòng 1 chứa hai số nguyên dương \(𝑛 \leq 5.10^5, 𝑘 \leq 𝑛\)
- Dòng 2 chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛 (\forall 𝑖: 𝑎_𝑖 \leq 10^6)\)
Output
- Ghi ra \(𝑛 − 𝑘 + 1\) dòng, dòng thứ \(𝑖\) ghi giá trị nhỏ nhất trong các phần tử \(𝑎_𝑖, 𝑎_{𝑖+1}, … , 𝑎_{𝑖+𝑘−1}\)
Các số trên một dòng của Input files được ghi cách nhau ít nhất một dấu cách
Scoring
- Subtask \(1\) (\(33.3\%\) số điểm): \(𝑛 \leq 10^3, 𝑘 \leq 𝑛\)
- Subtask \(2\) (\(19.1\%\) số điểm): \(𝑛 \times k \leq 10^7, 𝑘 \leq 𝑛\)
- Subtask \(3\) (\(47.6\%\) số điểm): \(𝑛 \leq 5 \times 10^5, 𝑘 \leq 𝑛\)
Example
Test 1
Input
5 3
2 1 5 3 4 Output
1
1
3
Bình luận
include <bits/stdc++.h>
using namespace std;
int n, k, a[int(1e6 + 7)];
deque<pair\<int, int> > dq;
int main()
{
//freopen("MINIMUM.inp", "r", stdin);
//freopen("MINIMUM.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
while(dq.size() && dq.front().second < i - k + 1)
dq.pop_front();
while(dq.size() && dq.back().first >= a[i])
dq.pop_back();
dq.push_back({a[i], i});
if(i >= k)
cout << dq.front().first << endl;
}
}
8 bình luận nữa