题目描述
在一个10000*10000的二维平面上，有n颗糖果。
LYK喜欢吃糖果！并且它给自己立了规定，一定要吃其中的至少C颗糖果！
事与愿违，LYK只被允许圈出一个正方形，它只能吃在正方形里面的糖果。并且它需要支付正方形边长的价钱。
LYK为了满足自己的求食欲，它不得不花钱来圈一个正方形，但它想花的钱尽可能少，你能帮帮它吗？
输入格式(square.in)
第一行两个数C和n。
接下来n行，每行两个数xi,yi表示糖果的坐标。
输出格式(square.out)
一个数表示答案。
输入样例
3 4
1 2
2 1
4 1
5 2
输出样例
4
样例解释
选择左上角在(1,1)，右下角在(4,4)的正方形，边长为4。
数据范围
对于30%的数据n<=10。
对于50%的数据n<=50。
对于80%的数据n<=300。
对于100%的数据n<=1000。1<=xi,yi<=10000。
分析：一个比较暴力的想法就是枚举边长，然后把所有符合要求的正方形计算一边看看有没有c个,这种做法在枚举边长上花的时间比较多，如果把枚举换成二分就会快很多，而且这道题是满足二分性质的，如果边长x都不能有c个糖果，那么x-1肯定没有c个糖果.二分一下每次检验是否能包含c个糖果即可.
这个检验比较有技巧性，可以想到的一个方法是前缀和，不过在做前缀和的时候要先离散化.标程给的方法非常好.先固定一个上边界，然后向下扩展，到刚好要超出x的时候把这两个边界中所有的点全部给提取出来，然后考虑左右边界，看第i个和第i+x个的横坐标相差是否≤x.这个方法好在可以很快地枚举出所有符合答案的矩形,也应用了一个思想：想要让(x,y)符合要求，那么先把符合要求的x给提出来，然后看看y是否符合要求.
存点不要存坐标，这也相当于离散化了坐标.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; int c, n, ans, b[]; struct node
{
int x, y;
}e[]; bool cmp(node a, node b)
{
return a.x < b.x;
} bool can(int l, int r, int len)
{
if (r - l + < c)
return false;
int cnt = ;
for (int i = l; i <= r; i++)
b[++cnt] = e[i].y;
sort(b + , b + + cnt);
for (int i = c; i <= cnt; i++)
if (b[i] - b[i - c + ] <= len)
return true;
return false;
} bool check(int len)
{
int cur = ;
for (int i = ; i <= n; i++)
{
if (e[i].x - e[cur].x > len)
{
if (can(cur, i - , len))
return true;
}
while (e[i].x - e[cur].x > len)
cur++;
}
if (can(cur, n, len))
return true;
return false;
} int main()
{
scanf("%d%d", &c, &n);
for (int i = ; i <= n; i++)
scanf("%d%d", &e[i].x, &e[i].y);
sort(e + , e + + n, cmp);
int l = , r = ;
while (l <= r)
{
int mid = (l + r) >> ;
if (check(mid))
{
ans = mid;
r = mid - ;
}
else
l = mid + ;
}
printf("%d\n", ans + ); return ;
}