1.整数二分

分巧克力

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int h[N],w[N];
int n,k;

bool check(int mid)
{
    int res=0;
    for(int i=0;i<n;i++)
    {
        res+=(h[i]/mid)*(w[i]/mid);
        if(res>=k) return true;
    }
   return false;
}

int main()
{
 cin>>n>>k;
    for(int i=0;i<n;i++) cin>>h[i]>>w[i];

    int l=1,r=1e5;
    while(l<r)
    {
        int mid=l+r+1>>1;//mid表示切得的正方形的最大边长
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<l<<endl;
    return 0;
}

冶炼金属

#include<bits/stdc++.h>
using namespace std;

int get(int a,int b)
{
    int l=1,r=1e9+1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(a/mid<=b) r=mid;
        else l=mid+1;
    }
    return r;
}

int main()
{
    int n; cin>>n;        
    int v_min=1,v_max=1e9;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        v_min=max(v_min,get(a,b));
        v_max=min(v_max,get(a,b-1)-1);
    }        
    printf("%d %d",v_min,v_max);
    return 0;
}

2.浮点二分

剪绳子

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,m;
int h[N];

bool check(double mid)
{
    int res=0;
    for(int i=0;i<n;i++)
    {
        res+=h[i]/mid;
        if(res>=m) return true;
    }
    return false;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>h[i];
    double l=0,r=1e9;
    while(r-l>1e-4)
    {
        double mid=(l+r)/2;//mid表示能剪出的最大长度
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2f",l);
    return 0;
}

3.(暴力+二分)

子串简写

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5*1e5+10;

int main()
{
    int k;
    string s;
    char c1,c2;
    vector<int>pc1; //储存c1的位置(下标)
    cin>>k>>s>>c1>>c2;

    //二分 O(n*logn)
    LL ans=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]==c1) 
        pc1.push_back(i);   //将c1下标存进来
        if(s[i]==c2)
            {
            //左条件表示当前枚举的c2前面的总长度都小于k
            //右条件表示c2前面没有出现过c1
                if(i+1<k||!pc1.size()) continue;
            //二分临界点:从右往左看,找出第一个满足不等式的数字    
                LL l=0,r=(int)pc1.size()-1;
                while(l<r)
                {
                    LL mid=l+r+1>>1;
                    if(pc1[mid]<=i-k+1) l=mid;//i即p2
                    else r=mid-1;
                }
                if(pc1[l]<=i-k+1) ans+=(l+1);
            }
    }
    cout<<ans<<endl;

/*    
//先枚举c1开头的字符,再枚举c2结尾的字符,最后利用长度判断
    int res=0;//暴力双指针写法 O(n^2)
    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=c1) continue;//下面不执行,进入下一次循环
        for(int j=i+1;j<s.size();j++)
        {
            int len=j-i+1;
            if(len>=k&&s[j]==c2)
            res++;
        }
    }
    cout<<res<<endl;
*/

    return 0;
}