二分查找 boj1028

SuperRock钟爱的香蕉Submit: 742   Accepted:556Time Limit: 1000MS  Memory Limit: 65536KDescription
Bupt的新水果店开张，有买一赠一的活动，即每买一只大小为A(1 <= A <= 1,000,000)的香蕉，他就能免费获得一只大小为B(1 <= B < A)的香蕉！
吝啬鬼SuperRock以及整个912实验室成员都喜欢香蕉，然而，这个活动是有规定的：大的一只香蕉必须是甜的，小的一只是不甜的。SuperRock并不在意：912里的都是狼，不管什么味道，香蕉总是一抢而光，他只想买最多的香蕉。
给出一组N(1 <= N <= 10,000)只甜香蕉的大小，M(1 <= M <= 10,000)只不甜的香蕉的大小，找出SuperRock最多能买多少只香蕉。注意：他能买甜的香蕉而不拿免费的不甜香蕉（店老板很高兴），但他不能直 接买不甜的香蕉（就是说，他只能通过赠送来获得）。
神哪，救一救SuperRock，找一个办法尽可能的喂饱那些狼吧。

Input
第 1 行: 两个用空格分开的整数，N和M。
第 2 至 N+1 行: 第i+1行包含一个整数，是第i只甜香蕉的大小。
第 N+2 至 N+M+1 行: 第i+N+1行包含一个整数，是第i只不甜的香蕉的大小。

Output
第 1 行: SuperRock能买的最大的香蕉的只数。

Sample Input

3 4
6
1
3
1
5
3
4


Sample Output

5

Hint
显 然，SuperRock能买所有的甜的香蕉。当他买了大小为6的甜香蕉，他可以免费拿任何一只不甜的香蕉（例如大小为3的）。当他买了大小为3的高质量香 蕉，他可以拿大小为1的免费不甜的香蕉。然而当他买了大小为1的甜干草，就不能拿不了免费香蕉了（因为大小必须严格小于）。这样，尽管SuperRock 很聪明，但他最多也只能拿5只香蕉了。

解题方法：
排序加二分查找。
bin_search中返回值是在non_sweet数组中小于target的所有值里面的最大值+1，取出它之后，调整rear值为rear = k - 2。如果没有可选的non_sweet值了，就break


#include 
#include 

int sweet[10010];
int non_sweet[10010];

int cmp(const void *a, const void *b)
{
    int *pa = (int *)a;
    int *pb = (int *)b;
    return (*pa - *pb);
}

int bin_search(int front, int rear, int target)
{
    int mid;
    while (front <= rear)
    {
        mid = (front + rear) / 2;
        if (non_sweet[mid] < target)
            front = mid + 1;
        else
            rear = mid - 1;
    }
    return front;
}

int main(int argc, char *argv[])
{
    int N, M, i, front, rear, k, ret;
    scanf("%d %d", &N, &M);
    for (i=0 ; i        scanf("%d", &sweet[i]);
    for (i=0 ; i        scanf("%d", &non_sweet[i]);

    qsort(sweet, N, sizeof(int), cmp);
    qsort(non_sweet, M, sizeof(int), cmp);
    front = ret = 0;
    rear = M - 1;
    for (i=N-1 ; i>=0 ; i--)
    {
        if (front >= rear)
            break;
        /* 每次选择小于甜香蕉sweet[i]的所有不甜的香蕉non_sweet中的最大值，并调整rear指，   即那些具有更大值的不甜的香蕉在以后都不可能被选择了 */
        k = bin_search(front, rear, sweet[i]);
        rear = k - 2;
        ret++;
    }
    ret += N;
    printf("%d\n", ret);
}