P2440 木材加工——题解

解题思路

二分木段长度 $x$。一根长度 $L_i$ 的原木可贡献 $\lfloor L_i/x floor$ 段，总段数至少为 $k$ 时说明 $x$ 可行，且所有更小长度也可行；否则需减小。记录最大的可行值。

复杂度分析

每次检查 $O(n)$，二分次数 $O(\log\max L_i)$，总时间 $O(n\log\max L_i)$，空间 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;long long k;cin>>n>>k;vector<int>a(n);int hi=0;for(int&i:a){cin>>i;hi=max(hi,i);}int lo=1,ans=0;
    while(lo<=hi){int mid=lo+(hi-lo)/2;long long cnt=0;for(int x:a){cnt+=x/mid;if(cnt>=k)break;}if(cnt>=k)ans=mid,lo=mid+1;else hi=mid-1;}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n;long long k;cin>>n>>k;vectora(n);int hi=0;for(int&i:a){cin>>i;hi=max(hi,i);}int lo=1,ans=0; while(lo<=hi){int mid=lo+(hi-lo)/2;long long cnt=0;for(int x:a){cnt+=x/mid;if(cnt>=k)break;}if(cnt>=k)ans=mid,lo=mid+1;else hi=mid-1;} cout<<ans<<'\n';return 0; }