PKU 1727

题意有些难理解：事件两个属性(t,x)，现在给定N个事件，另一个输入M，求在一个最近的时间点，在这个时间点内能通过M个诱发事件使得N个事件发生。

观察图中和题目中的公式，如果确定一个t2，那么我们要判断t2能否通过M个事件诱发所给的N个事件。如果t时刻能满足，那么t-1,t-2 等等前面的时刻也能满足（通俗的理解就是t越小，那么所能覆盖的面积越大）。要求最大的，那么能二分枚举t，从N个事件中t最小的作为上界，一个很小的数作为下界。另求一个t，最少需要多少个事件才能诱发所给的事件，通过给N个事件按x排序，维持一个x的范围，不断缩小，如果满足不了则增加一个点。

//948K    454MS
//二分 + 排序
#include <iostream>
#include <numeric>
#include <limits>
using namespace std;

const int MAX=100001;
int M,N;

typedef struct _Node{
    int t;
    int x;
}Node;

Node nodes[MAX];

int cmp(const void* left,const void* right)
{
    return ((Node*)left)->x-((Node*)right)->x;
}

bool Greedy(int t_now)
{
    int x_max;
    int x_min;
    int need=0;
    bool have_one=false;
    for(int i=0;i<N;i++)
    {
        if(!have_one)
        {
            x_max=nodes[i].x+abs(t_now-nodes[i].t);
            x_min=nodes[i].x-abs(t_now-nodes[i].t);
            have_one=true;
            need++;
            if(need>M)
                return false;
        }
        else
        {
            int t_max=nodes[i].x+abs(t_now-nodes[i].t);
            int t_min=nodes[i].x-abs(t_now-nodes[i].t);
            if(t_min>x_min)
                x_min=t_min;
            if(t_max<x_max)
                x_max=t_max;
            if(x_max<x_min)
            {
                have_one=false;
                i--;
            }
        }
    }
    if(need>M)
        return false;
    else
        return true;
}


int main()
{
    int K;
    scanf("%d",&K);
    int NUM=0;
    while(K--)
    {
        int lest=numeric_limits<int>::max();
        scanf("%d%d",&N,&M);
        for(int i=0;i<N;i++)
        {
            scanf("%d%d",&nodes[i].t,&nodes[i].x);
            if(nodes[i].t<lest)
                lest=nodes[i].t;
        }
        qsort(nodes,N,sizeof(Node),cmp);

        int up=lest;
        int down=-4000000;
        
        while(up>=down)
        {
            int mid=(up+down)/2;
            //cout<
            if(Greedy(mid))
                down=mid+1;
            else
                up=mid-1;
        }
        printf("Case %d: %d\n",++NUM,up);
    }
}