常用技巧：二分搜索

二分不仅是简单的一个查找工具，而且是一种类型题目的解体思路。困在了一道题上：求最大值的最小（大概是这种类型......）遇到这种情况应该考虑二分查找。先将可能的最大值列出来，对该数列排序，在该数列上进行二分，判断当前节点是否合适，由此求出最大值的最小值。
例题洛谷P1182、P1642，这里以P1642为例（二分+最短路）

#include<bits/stdc++.h>
using namespace std;
int n,m,b;
int fee[10005],cfee[10005];
struct edge
{
    int next,cost;
};
vector<edge> edges[10005];

bool mark[10005];
struct node
{
    int index;
    long long dis;
    bool operator <(const node &x) const
    {
        return x.dis<dis;
    }
};
long long dis[10005];
priority_queue<node> q;

bool check(int x)
{
    if(fee[1]>x||fee[n]>x){
        return false;
    }
    while(!q.empty()){
        q.pop();
    }
    for(int i=1;i<=n;i++){
        if(fee[i]>x){
            mark[i]=true;
        }
        else{
            mark[i]=false;
        }
        dis[i]=0x7fffffffffffffff;
    }

    dis[1]=0;
    q.push((node){1,0});
    while(!q.empty()){
        node now=q.top();
        q.pop();
        if(mark[now.index]){
            continue;
        }
        mark[now.index]=true;
        for(int i=0;i<edges[now.index].size();i++){
            int next=edges[now.index][i].next;
            if(mark[next]){
                continue;
            }
            int cost=edges[now.index][i].cost;
            if(dis[next]>now.dis+cost){
                dis[next]=now.dis+cost;
                q.push((node){next,dis[next]});
            }
        }
    }
    if(dis[n]<=b){
        return true;
    }
    else{
        return false;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&fee[i]);
        cfee[i]=fee[i];
        edges[i].clear();
    }
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a==b){
            continue;
        }
        edge temp;
        temp.next=b;
        temp.cost=c;
        edges[a].push_back(temp);
        temp.next=a;
        edges[b].push_back(temp);
    }
    sort(cfee+1,cfee+n+1);
    if(!check(cfee[n])){
        printf("AFK\n");
        return 0;
    }
    int l=1,r=n,ans=cfee[n];
    while(l<=r){
        int mid=(l+r)/2;
        if(check(cfee[mid])){
            r=mid-1;
            ans=cfee[mid];
        }
        else{
            l=mid+1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

这类型题应该立马想到二分。难点主要在于怎么构建出二分数列以及怎么判断。
对于浮点数的二分查找，需要注意精度的问题。通常两种方法，第一种是为循环设置结束的最低精度，第二种是设定最大循环数（后者比较保险）。POJ1064，很多细节，需要时常看一下

#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
#define eps 1e-10
int n,m;
double len[10005];
bool judge(double mid){
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=(int)(len[i]/mid);
    }
    return ans>=m;
}
int main(){
    scanf("%d%d",&n,&m);
    double l=0,r=0.0,ans;
    bool flag=false;
    for(int i=1;i<=n;i++){
        scanf("%lf",&len[i]);
        r=max(r,len[i]);
    }
    for(int i=1;i<=100;i++){
        double mid=(l+r)/2;
        if(judge(mid)){
            l=mid;
            flag=true;
            ans=mid;
        }
        else{
            r=mid;
        }
    }
    if(flag) printf("%.2f\n",floor(ans*100)/100);
    else printf("0.00\n");
    return 0;
}

除了上面提到的最大化最小值，类似的还有最大化平均值。【有n个物品的重量和价值分别为wi和vi，从中选出k个物品使得单位重量的价值最大】不是简单的贪心，在这里是要求总价值/总重量。这种情况可以二分，判断当前的单位重量价值有没有可能用前k个物品来实现。POJ3111

#include<stdio.h>
#include<algorithm>
using namespace std;
int n,k,ans[100005];
struct item{
    int loc;
    double value,weight,tmp;
    bool operator <(const item &A) const{
        return tmp>A.tmp;
    }
}items[100005];
bool judge(double x){
    for(int i=1;i<=n;i++){
        items[i].tmp=items[i].value-x*items[i].weight;
    }
    sort(items+1,items+n+1);
    double sum=0;
    for(int i=1;i<=k;i++){
        sum+=items[i].tmp;
        ans[i]=items[i].loc;
    }
    return sum>=0;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&items[i].value,&items[i].weight);
        items[i].loc=i;
    }
    double l=0,r=10000005;
    for(int i=1;i<=100;i++){
        double mid=(l+r)/2;
        if(judge(mid)) l=mid;
        else r=mid;
    }
    for(int i=1;i<=k;i++){
        if(i!=1) printf(" ");
        printf("%d",ans[i]);
    }
    return 0;
}

使用二分的另一类型题：求第m个大的数，POJ3685。

POJ2010，因为最后结果只与中位数成绩有关与其他成绩无关，那么对每个成绩进行记录比他小的成绩里最小的(n-1)/2个f的和，以及比他大的成绩里最小的(n-1)/2个f的和。最后二分就行

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,c,f,h,left[100005],right[100005],ans;
struct cow{
    int s,f;
    bool operator < (const cow &x) const{
        return s<x.s;
    }
}cows[100005];
priority_queue<int> que;

int main(){
    scanf("%d%d%d",&n,&c,&f);
    for(int i=1;i<=c;i++){
        scanf("%d%d",&cows[i].s,&cows[i].f);
    }
    sort(cows+1,cows+c+1);
    h=(n-1)/2;

    int sum=0;
    while(!que.empty()) que.pop();
    for(int i=1;i<=c;i++){
        left[i]=sum;
        if(i<=h){
            sum+=cows[i].f;
            que.push(cows[i].f);
        }
        else{
            if(cows[i].f<que.top()){
                sum-=que.top();
                que.pop();
                que.push(cows[i].f);
                sum+=cows[i].f;
            }
        }
    }

    sum=0;
    while(!que.empty()) que.pop();
    for(int i=c;i>=1;i--){
        right[i]=sum;
        if(c-i+1<=h){
            sum+=cows[i].f;
            que.push(cows[i].f);
        }
        else{
            if(cows[i].f<que.top()){
                sum-=que.top();
                que.pop();
                que.push(cows[i].f);
                sum+=cows[i].f;
            }
        }
    }

    bool flag=false;
    for(int i=c-h;i>=h+1;i--){
        if(left[i]+cows[i].f+right[i]<=f){
            flag=true;
            printf("%d\n",cows[i].s);
            return 0;
        }
    }
    if(!flag) printf("-1\n");
}