Longest Staircase
Autumn Tournament (2023)
Submission name: stairs.cpp
Problem summary
Choose and arrange as many blocks as possible in a strictly increasing staircase. Each increase between adjacent block heights must be at most K. Each block can be used once.
Input
N K, followed by N positive block heights.
Output
The maximum number of steps.
Constraints
3 ≤ N ≤ 1000000; 3 ≤ K ≤ 1000000; heights ≤ 100000000.
Worked example
Original statement sample.
Input
5 7 7 20 16 29 15
Output
3
Solution analysis
- Sort the heights. A staircase must use distinct heights, so equal-height blocks cannot contribute extra steps; discard duplicates.
- Among the sorted distinct heights, a gap greater than K separates two groups that no valid staircase can join. Inside a group, taking every height is valid and cannot be improved by skipping a block. Track the longest group.
- The sample becomes 7, 15, 16, 20, 29. The gaps 8 and 9 split it into [7], [15,16,20], [29], so the answer is 3.
Why it works
A gap greater than K cannot be bridged because no available height lies inside that gap. Conversely every consecutive gap in a group is valid, so all its distinct blocks form a staircase. The largest group is optimal.
Watch out. Duplicates must not create extra steps. The original input order does not restrict the staircase.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,limit;
cin>>n>>limit;
vector<int>heights(n);
for(int&height:heights){
cin>>height;
}
sort(heights.begin(),heights.end());
heights.erase(unique(heights.begin(),heights.end()),heights.end());
int current=1;
int answer=1;
for(int i=1;i<static_cast<int>(heights.size());i++){
// A large gap starts a new independently usable group.
if(heights[i]-heights[i-1]<=limit){
current++;
}
else{
current=1;
}
answer=max(answer,current);
}
cout<<answer<<'\n';
}