Minimum Cabinet Width
National Olympiad — Regional round
Submission name: vases.cpp
Problem summary
Arrange N vases of unit width on horizontal shelves spanning a cabinet. Vase heights are Aᵢ. Each compartment must be at least as tall as its tallest vase; compartment heights sum to at most H, and shelf thickness is negligible. Reordering vases is allowed. Minimize the cabinet width.
Input
N H, then N vase heights.
Output
Minimum integer cabinet width.
Constraints
1 ≤ N,H ≤ 10⁷; 1 ≤ Aᵢ ≤ H.
Worked example
An independently prepared example for this explanation.
Input
5 6 4 3 2 1 1
Output
3
Solution analysis
- Sort heights descending using a frequency array. For candidate width w, pack consecutive groups of at most w vases: the required height is A₀+A_w+A₂w+….
- Binary-search the smallest width with required height at most H. The sum of all vase heights divided by H is a useful lower bound on width.
Why it works
For the first jw+1 tallest vases, at least j+1 compartments are needed, so the (j+1)-st largest compartment maximum is at least A_jw. Grouping consecutive sorted vases attains all these bounds simultaneously. Increasing width cannot increase required height, justifying binary search.
Watch out. N reaches ten million; counting sort exploits the bounded heights. Required-height sums need 64 bits.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: For the first jw+1 tallest vases, at least j+1 compartments are needed, so the (j+1)-st
// largest compartment maximum is at least A_jw. Grouping consecutive sorted vases attains all these
// bounds simultaneously.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,h;
cin>>n>>h;
vector<int>freq(h+1);
long long total=0;
for(int i=0;i<n;i++){
int x;
cin>>x;
freq[x]++;
total+=x;
}
vector<int>a;
a.reserve(n);
for(int x=h;x>=1;x--){
while(freq[x]--){
a.push_back(x);
}
}
int lo=max(1LL,(total+h-1)/h),hi=n;
while(lo<hi){
int w=lo+(hi-lo)/2;
long long need=0;
for(int i=0;i<n&&need<=h;i+=w){
need+=a[i];
}
if(need<=h){
hi=w;
}
else{
lo=w+1;
}
}
cout<<lo<<'\n';
}