洛谷P2440 木材加工
很简单的二分,答案具有单调性,如果超过最优解则无法分成k份,不合法,如果没有短于最优解,则一定合法,这样问题的求解就具备了单调性
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int n,k;
bool valid(int x)
{
int cnt=0;
for(int i=1;i<=n;i++)
{
cnt+=(a[i]/x);
}
if(cnt<k) return false;
else return true;
}
int main()
{
cin>>n>>k;
int maxn=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
maxn=max(maxn,a[i]);
}
int l=0,r=maxn;
while(l<r)
{
int mid=l+r+1>>1;
if(valid(mid)) l=mid;
else r=mid-1;
}
cout<<l;
}
以上可作为二分问题的标准模板