二分（二分答案）问题合集

二分问题有很明显的关键字如：最大值最小，最小值最大。
或者在数据上发现只有log级别才能接受时，我们都应该优先考虑二分。
二分问题的难点也不在二分，而是如何使用贪心配合二分，贪心策略往往是难点所在。

C. Schedule Management

题意：n个工人，m个任务，每个任务都指定哪个工人适合这个任务，如果由适合的工人来做这个任务就只花费1小时，否则要花费2小时。求最少花费多少小时

关键字：花费时间最小。

思路：贪心思路是，如果对于我们规定时间，这个工人完成不所有指定任务，那么就把所有没完成的任务累加起来，可以完成任务的工人要利用起来去帮助完成这些多出的任务。

值得注意的是：我们需要先统计出所有工人不能完成的任务数，然后再去找人帮忙，不能凭空帮忙。

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 2e5+100;
int a[N],n,m;
bool check(int num)
{
    
    int sum=0;
    for(int i=1;i<=n;i++)
    {
    
        if(a[i]>num)
        {
    
            sum+=a[i]-num;
        }
        else
        {
    
            sum-=(num-a[i])/2;
            sum=max(sum,0);
        }
    }
    return sum==0?true:false;
}
bool cmp(int a,int b)
{
    
    return a>b;
}
int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        cin>>n>>m;
        for(int i=1,temp;i<=m;i++)
        {
    
            cin>>temp;
            a[temp]++;
        }
        sort(a+1,a+n+1,cmp);
        int l=0,r=2*m;
        while(l<=r)
        {
    
            int mid=(l+r)/2;
            if(check(mid))
            {
    
                r=mid-1;
            }
            else
            {
    
                l=mid+1;
            }
        }
        cout<<l<<endl;
        for(int i=1;i<=n;i++)
        {
    
            a[i]=0;
        }
    }
    return 0;
}

精度相关的二分问题
P1577 切绳子

#include <bits/stdc++.h>
using namespace std;
double a[10000+10],l,r=1000000,mid;
int n,k;
bool check(double mid){
    
    int ans=0;
    for(int i=1;i<=n;i++)
       ans+=a[i]/mid;
    return ans>=k;
}
int main(){
    
    //freopen("in.txt","r",stdin);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    while(r-l>=0.001){
    
        mid=(l+r)/2.0;
        if(check(mid))
            l=mid+0.001;
        else
            r=mid-0.001;
    }
    cout<<r<<endl;
    return 0;
}

TO BE CONTINUE。。。