POJ 1727 Advanced Causal Measurements (ACM) (二分+贪心)

这个题开始没读懂，很久才明白，题目是要寻找在所有点之下（两条直线的下面）的m个点中最小的t值的最大值，然后又想了很久，没想出好办法，看到discuss是二分，才想到二分答案，开始对每个点进行排序，对每个点做斜率为-1的线，与y轴相较，按照交点的大小进行从小到大的顺序排序，原因就是当二分答案时，利用贪心的思想对这些点遍历，很容易就可以计算出最少需要多少个因事件，（很多谈心题目也都是利用这一点来贪心的），二分过后，输出最大的t值就可以了。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
using namespace std;

#define MAXN 100050
#define INF (1<<30)
#define CLR(x,y) (memset(x,y,sizoef(x)))
int gi,gj,n,gn,r_val,m;
struct Node{
    int x,y;
    int val;
}node[MAXN];
bool cmp(const Node& a,const Node& b)
{
    return a.val<b.val;
}
inline bool _is(const int& val)
{
    gn = 1;
    r_val = node[0].x + node[0].y - val;
    for(gi = 1; gi < n; ++gi)
    {
        if(node[gi].x-node[gi].y+val > r_val)
        {
            r_val = node[gi].x + node[gi].y - val;
            ++gn;
        }
        if(gn > m )
            return false;
    }
    return true;
}
int main()
{
    int b_mid,b_low,b_high,ans,tt;
    int i,j,tmp,mmin,ttt;
    scanf("%d",&tt);
    ttt = 0;
    while(tt--)
    {
        ++ttt;
        b_low = -2000050;
        scanf("%d %d",&n,&m);
        mmin = INF;
        for(i = 0; i < n; ++i)
        {
            scanf("%d%d",&node[i].y,&node[i].x);
            node[i].val = node[i].x+node[i].y;
            mmin = mmin<node[i].y?mmin:node[i].y;
        }
        b_high = mmin;
        sort(node,node+n,cmp);
        while(b_low <= b_high)
        {
            b_mid = (b_low+b_high)>>1;
            if(_is(b_mid))
            {
                ans = b_mid;
                b_low = b_mid+1;
            }else
                b_high = b_mid-1;
        }
        printf("Case %d: %d\n",ttt,ans);
    }
    return 0;
}