63 lines
1.8 KiB
C++
63 lines
1.8 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
|
|
using namespace std;
|
|
|
|
using Range = pair<int, int>;
|
|
|
|
void log_range_vector(const vector<Range>& ranges, const string& prefix = "") {
|
|
clog << prefix;
|
|
for (const Range& r : ranges) {
|
|
clog << "(" << r.first << "," << r.second << ")" << " ";
|
|
}
|
|
clog << endl;
|
|
}
|
|
|
|
size_t get_min_ranges_amount(vector<Range> ranges, Range full_range) {
|
|
sort(ranges.begin(), ranges.end());
|
|
log_range_vector(ranges, "ranges: ");
|
|
size_t i = 0, ans = 0;
|
|
while (ranges[i].second < full_range.first) { i++; }
|
|
int max_start = 0, current_end = ranges[i].second;
|
|
while (true) {
|
|
while (ranges[i].first <= max_start) {
|
|
current_end = max(current_end, ranges[i].second);
|
|
if (current_end >= full_range.second) { return ans + 1; }
|
|
i++;
|
|
if (i >= ranges.size()) { throw invalid_argument("No valid ranges found (inside loop)"); }
|
|
}
|
|
ans++;
|
|
if (current_end >= full_range.second) { return ans; }
|
|
max_start = current_end;
|
|
}
|
|
throw invalid_argument("No valid ranges found (outside loop)");
|
|
}
|
|
|
|
vector<Range> get_ranges(const vector<int>& monitors) {
|
|
vector<Range> ranges;
|
|
for (int i = 0; i < monitors.size(); i++) {
|
|
ranges.emplace_back(i - monitors[i], i + monitors[i] + 1);
|
|
}
|
|
return ranges;
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
|
|
size_t monitors_amount;
|
|
cin >> monitors_amount;
|
|
vector<int> monitors(monitors_amount);
|
|
for (int i = 0; i < monitors_amount; i++) {
|
|
cin >> monitors[i];
|
|
}
|
|
vector<Range> ranges = get_ranges(monitors);
|
|
Range full_range = {0, monitors_amount};
|
|
|
|
cout << get_min_ranges_amount(ranges, full_range) << endl;
|
|
|
|
|
|
return 0;
|
|
}
|