Fastest Road Segment
National Olympiad — National round (2021 season)
Submission name: trip.cpp
Problem summary
A road consists of N one-metre sections with given traversal times. Find a contiguous segment of M metres with minimum total time. Break ties by choosing the segment farthest from the road start. Report its starting distance from the start, in metres.
Input
N M and the N traversal times.
Output
The zero-based starting distance of the selected segment.
Constraints
0 < N ≤ 10,000,000; 0 < M ≤ N; 0 < times ≤ 1000.
Worked example
An independently prepared example for this explanation.
Input
6 3 6 5 4 4 6 3
Output
3
Solution analysis
- A fixed-length sliding window gives each M-section total in constant update time: add the entering time and subtract the leaving time.
- Store the last M values in a circular buffer. Save a new best window whenever its sum is less than or equal to the old best, so later equal windows win.
- The sample window sums are 15,13,14,13. The two best windows start at distances 1 and 3; the farther one starts at distance 3. A section numbered four begins three metres from the road start.
Why it works
At each completed window, the rolling sum contains exactly its M traversal times because the overwritten buffer entry is precisely the departing value. Every possible start is considered. Replacing on equal sums selects the greatest start among all minimum sums.
Watch out. The output is a distance beginning at 0, not a one-based section index. Equal sums must replace the earlier best.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> buffer(m);
long long sum = 0;
long long best = numeric_limits<long long>::max();
int answer = 0;
for (int i = 0; i < n; i++) {
int value;
cin >> value;
int slot = i % m;
if (i >= m) {
sum -= buffer[slot];
}
buffer[slot] = value;
sum += value;
// Replacing on equality keeps the farthest minimum-time window.
if (i >= m - 1 && sum <= best) {
best = sum;
answer = i - m + 1;
}
}
cout << answer << '\n';
}