A collection of dichotomous (dichotomous answers) questions

Dichotomous questions have obvious keywords such as ： The maximum is the smallest , The minimum is the maximum .
Or only log When the level is acceptable , We should all give priority to two points .
The difficulty of dichotomy is not dichotomy , But how to use greed to cooperate with dichotomy , Greedy strategy is often the difficulty .

C. Schedule Management

The question ：n One worker ,m A mission , Each task specifies which worker is suitable for the task , If the right workers do this task, it will only cost 1 Hours , Otherwise, it will cost 2 Hours . Ask how many hours it will take at least

keyword ： Take the least time .

Ideas ： Greedy thinking is , If we set a time , This worker can't complete all the assigned tasks , Then add up all the unfinished tasks , Workers who can complete the task should use it to help complete these extra tasks .

It is worth noting that ： We need to count the number of tasks that all workers cannot complete , Then ask someone to help , You can't help out of thin air .

#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;
}

Accuracy related dichotomy
P1577 Cut the rope

#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...