二分

一、二分

C++ STL的二分查找函数：

binary_search　　返回bool值，是否存在。

lower_bound　　返回可插入的最小值的迭代器，即返回第一个符合条件的元素位置。（从已排好序的序列a中利用二分搜索，找出ai>=k的ai的最小指针）

upper_bound　　返回可插入的最大位置的迭代器，即返回最后一个符合条件的元素位置。（ai>k）

例：CF706B

/*binary_search自己第一次写的*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstdlib>

using namespace std;

const int maxn = 100005;

int a[maxn],b[maxn],m;
int binary(int x)
{
    int low=0,hight=m-1;
    int mid;
    mid=(hight-low)/2+low;
    while(low<=hight)
    {
        if(x==a[mid]&&a[mid+1]!=a[mid])
            return mid+1;
        else if(x<a[mid])
            hight=mid-1;
        else
            low=mid+1;
        mid=(hight-low)/2+low;
    }
}
int main()
{
    int i,q;
    //freopen("Atext.in","r",stdin);
    cin >> m;
    for(i=0;i<m;i++)
        cin >> a[i];
    cin >> q;
    sort(a,a+m);
    for(i=0;i<q;i++)
        cin >> b[i];
    for(i=0;i<q;i++)
    {
        if(b[i]>=a[m-1])
            cout << m << endl;
        else
            cout << binary(b[i]) << endl;
    }
    return 0;
}

1.其中，如果寻找的value存在，那么lower_bound返回一个迭代器指向其中第一个这个元素。upper_bound返回一个迭代器指向其中最后一个这个元素的下一个位置（明确点说就是返回在不破坏顺序的情况下，可插入value的最后一个位置）。如果寻找的value不存在，那么lower_bound和upper_bound都返回“假设这样的元素存在时应该出现的位置”。（= =杠掉的部分是我看了个假视频）。函数lower_bound()在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置，且last的位置是越界的！！要指出的是lower_bound和upper_bound在源码中只是变换了if--else语句判定条件的顺序，就产生了最终迭代器位置不同的效果。

2.binary_serach试图在已排序的[first，last）中寻找元素value,若存在就返回ture，若不存在则返回false。返回单纯的布尔值也许不能满足需求，而lower_bound，upper_bound能提供额外的信息。事实上由源码可知，binary_serach便是利用lower_bound求出元素应该出现的位置，然后再比较该位置的值与value值。该函数有两个版本一个是operator<，另外一个是利用仿函数comp进行比较。

/*p是严格不重复单调递增的序列
  q是小明猜的数字，随机有重复
  对每一个q在p中进行查找，找到相同的就记录该值
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 1000005

using namespace std;
int p[maxn],q[maxn];
int main()
{
    long long n,m,i,sum=0;
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    cin >> n >> m;
    for(i=1;i<=n;i++)         //从1开始，因为lower_bound与upper_bound一定会返回一个值，防止查找不到时越界
        cin >> p[i];
    for(i=1;i<=m;i++)                             //O(n)
    {
        cin >> q[i];
        if(q[i]==p[lower_bound(p,p+n,q[i])-p])   //O(logn)
            sum+=q[i];
    }
    cout << sum << endl;
    return 0;
}

/*查找x在一个数列a中重复出现的次数*/
#include <iostream>
#include <algorithm>
#include <cstring>
#define maxn 100005

using namespace std;
int a[maxn];
int main()
{
    int n,m,Q,i;
    while(cin >> n >> m)
    {
        for(i=1;i<=n;i++)
            cin >> a[i];
        sort(a,a+n);
        for(i=0;i<m;i++)
        {
            cin >> Q;
            int k=upper_bound(a+1,a+n+1,Q)-lower_bound(a+1,a+1+n,Q);
            cout << k << endl;
        }
    }
    return 0;
}

3.应用：二分答案+检验。对于难以直接确定解的问题，采取二分枚举+检验的思想将求解类问题转换为验证类问题。

例：POJ1064　　http://poj.org/problem?id=1064

题目大意：有n条绳子，它们的长度为Li，从它们中切割出k条相等长度绳子，这k条绳子每条最长能有多长；

像这样在求解最大化或最小化问题中，能够比较简单的判断条件是否满足，那么使用二分枚举答案就可以很好的解决问题;

Cable master

Description

Inhabitants of the Wonderland have decided to hold a regional programming contest. The Judging Committee has volunteered and has promised to organize the most honest contest ever. It was decided to connect computers for the contestants using a "star" topology - i.e. connect them all to a single central hub. To organize a truly honest contest, the Head of the Judging Committee has decreed to place all contestants evenly around the hub on an equal distance from it.
To buy network cables, the Judging Committee has contacted a local network solutions provider with a request to sell for them a specified number of cables with equal lengths. The Judging Committee wants the cables to be as long as possible to sit contestants as far from each other as possible.
The Cable Master of the company was assigned to the task. He knows the length of each cable in the stock up to a centimeter,and he can cut them with a centimeter precision being told the length of the pieces he must cut. However, this time, the length is not known and the Cable Master is completely puzzled.
You are to help the Cable Master, by writing a program that will determine the maximal possible length of a cable piece that can be cut from the cables in the stock, to get the specified number of pieces.

Input

The first line of the input file contains two integer numb ers N and K, separated by a space. N (1 = N = 10000) is the number of cables in the stock, and K (1 = K = 10000) is the number of requested pieces. The first line is followed by N lines with one number per line, that specify the length of each cable in the stock in meters. All cables are at least 1 meter and at most 100 kilometers in length. All lengths in the input file are written with a centimeter precision, with exactly two digits after a decimal point.

Output

Write to the output file the maximal length (in meters) of the pieces that Cable Master may cut from the cables in the stock to get the requested number of pieces. The number must be written with a centimeter precision, with exactly two digits after a decimal point.
If it is not possible to cut the requested number of pieces each one being at least one centimeter long, then the output file must contain the single number "0.00" (without quotes).

Sample Input

Sample Output

2.00

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double eps=0.0001;
const int maxn=10005;
int n,k;
double L[maxn];
bool cc(double x)           //对于枚举的x的长度，判断其是否满足k个的要求;
{
    int cnt=0;
    for(int i=0;i<n;i++)
        cnt+=(int)(L[i]/x);
    return cnt>=k;
}
void solve()
{
    double l=0,r=200005;    //题目是1m--100km,这里又WA了一回;
    while(r-l>=eps){        //可以把终止条件设为一个指定的区间大小，也可以设为循环次数，但注意不要因为精度过高而死循环;
        double mid=(l+r)/2.0;
        if(cc(mid))l=mid;
        else    r=mid;
    }
    //printf("%.2lf
",r);              感觉这里应该有浮点误差，不加floor函数的不到正确值
    printf("%.2lf
",floor(r*100)/100); //幸好样例给的好，不然WA了，完全找不出来0.0;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%lf",&L[i]);
    solve();
    return 0;
}

最大化平均值，01规划，最大化最小值，最小化最大值。

例：http://codeforces.com/contest/626/problem/C

#include <bits/stdc++.h>

using namespace std;
//这二分用的太精致了,妙呀QAQ;
int n,m;
bool check(int x)//二分的判定基本都是用贪心去check;
{
    int num1=x/2;
    int num2=x/3;
    int num3=x/6;
    if(num1<n)return false;
    if(num2<m)return false;
    if(min(num3,num1-n)<m-(num2-num3))return false;//判断2，3的公倍数尽量满足是否成立；
    else return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    int l=0,r=1e7,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))ans=mid,r=mid-1;
        else  l=mid+1;
    }
    cout << ans << endl;
    return 0;
}