二分答案即将求值问题转化为判断问题
14356: 工资
题目描述
n+e在暑假参加了打零⼯的活动，这个活动分为n个⼯作日，每个⼯作日的⼯资为Vi。有m个结算⼯钱的时间,n+e可以*安排这些时间，也就是说什么时候拿钱，老板说的不算，n+e才有发⾔权！（因为n+e是⼟豪，他是老板的老板）
n+e不喜欢身上⼀次性有太多的钱，于是他想安排⼀下拿钱的时间，使他⼀次性拿的钱中最⼤的那次的最小。（最后⼀天⼀定要领钱）
输入
第⼀⾏2个数n,m
接下来n⾏，每⾏⼀个数，代表Vi
输出
输出⼀⾏⼀个整数，表示最小的最⼤钱数。
样例输入 Copy
7 5 100 400 300 100 500 101 400
样例输出 Copy
500
提示
100 400//300 100//500//101//400// ”//” 表示 n+e 要去拿钱。
对于20%的数据，1<=n<=20
对于另20%的数据，1≤n≤50,Vi的和不超过1000
对于100%的数据，1≤n≤100000,m≤n,Vi≤100000
一道二分答案题目
代码：
#include <iostream>
using namespace std;
typedef long long ll;
ll n,m,ans,l,r,i,mid;
ll a[100005];
bool check(ll mid)
{
ll cnt=1,sum=0;
for(int i=0;i<n;i++)
{
if(a[i]>mid) return false;
sum+=a[i];
if(sum>mid) {sum=a[i];cnt++;}
}
if(cnt>m) return false;
else return true;
} //check()函数判断答案是否可行
int main()
{
cin>>n>>m;
l=r=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
r+=a[i];
}
while(l+1<r)
{
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
} //二分找最小答案
cout<<r;
return 0;
}
P2440 木材加工
木材厂有 n 根原木，现在想把这些木头切割成 k段长度均为 l 的小段木头（木头有可能有剩余）。
当然，我们希望得到的小段木头越长越好，请求出 l 的最大值。
木头长度的单位是 cm，原木的长度都是正整数，我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 11和 21，要求切割成等长的 6 段，很明显能切割出来的小段木头长度最长为 5。
输入格式
第一行是两个正整数 n,k分别表示原木的数量，需要得到的小段的数量。
接下来 nn行，每行一个正i，表示一根原木的长度。
输出格式
仅一行，即 l 的最大值。
如果连 1cm 长的小段都切不出来，输出 0。
输入
3 7 232 124 456
输出
114
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100005];
ll n,k,i,ans,l,r,lmax=0,mid;
bool check(ll mid)
{
long long sum=0;
for(int i=0;i<n;i++)
sum+=a[i]/mid;
return sum>=k;
}
int main()
{
cin>>n>>k;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
lmax=max(lmax,a[i]);
}
l=ans=0;r=lmax+1;
while(l+1<r)
{
mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l;
return 0;
}
//二分答案
二分答案一般模板
bool check(int mid)
{
}//判断答案是否可行
int main()
{
int l,r,mid;
l=minans,r=maxans;
while(l+1<r)
{
mid=(l+r)/2;
if(check(mid)) ...
else ...//根据题目判断
}
return 0;
}例1 找答案中最大的 例2 找答案中最小的 二分写法不同。