Chain Orders
National Olympiad — Municipal round
Submission name: storage.cpp
Problem summary
Fulfil N chain orders of lengths Lᵢ. One opened link can detach an ordered chain from the spool and leave one loose opened link. Loose links can be assembled into other ordered chains without additional openings. Find the minimum openings, allowing any order of processing.
Input
N and the N lengths.
Output
The minimum number of opened links.
Constraints
1 ≤ N ≤ 100,000; 1 ≤ Lᵢ ≤ 100,000.
Worked example
An independently prepared example for this explanation.
Input
4 1 1 8 9
Output
2
Solution analysis
- If t orders are assembled from loose links, N−t spool operations can supply N−t links.
- Choose the t shortest orders. Find the largest t whose total length is at most N−t.
Why it works
Any selection of t assembled orders needs at least the sum of the t shortest lengths. Conversely those orders can be assembled after executing the remaining spool orders, so the inequality is both necessary and sufficient.
Watch out. Loose links are already opened, so joining them needs no further opening operation.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Any selection of t assembled orders needs at least the sum of the t shortest lengths.
// Conversely those orders can be assembled after executing the remaining spool orders, so the
// inequality is both necessary and sufficient.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>a(n);
for(int&x:a){
cin>>x;
}
sort(a.begin(),a.end());
long long sum=0;
int t=0;
while(t<n&&sum+a[t]<=n-t-1){
sum+=a[t++];
}
cout<<n-t<<'\n';
}