栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

二分法&&双指针判定:赶牛入圈

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

二分法&&双指针判定:赶牛入圈

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的,而且至少要包含 CC 单位的三叶草,来当做它们的下午茶。

畜栏的边缘必须与 X,YX,Y 轴平行。

约翰的土地里一共包含 NN 单位的三叶草,每单位三叶草位于一个 1×11×1 的土地区域内,区域位置由其左下角坐标表示,并且区域左下角的 X,YX,Y 坐标都为整数,范围在 11 到 1000010000 以内。

多个单位的三叶草可能会位于同一个 1×11×1 的区域内,因为这个原因,在接下来的输入中,同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中,才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下,能包含至少 CC 单位面积三叶草的情况下,畜栏的最小边长是多少。

输入格式

第一行输入两个整数 CC 和 NN。

接下来 NN 行,每行输入两个整数 XX 和 YY,代表三叶草所在的区域的 X,YX,Y 坐标。

同一行数据用空格隔开。

输出格式

输出一个整数,代表畜栏的最小边长。

数据范围

1≤C≤5001≤C≤500,
C≤N≤500C≤N≤500

输入样例:

3 4
1 2
2 1
4 1
5 2

输出样例:

4

代码如下:

#include 
using namespace std;
const int N=510;
int n,m,c,i,j,k;
pair a[N];
inline int check(int now)//双指针判定:大致就是,我们有一个指针i和一个指针j,他们两个负责记录,满足条件的区间的左端点,和右端点.
//我们这里显然就是要,检测x坐标在指定区域,y坐标在指定区域.
{
    for(int i=1;i<=n;i++)
    {
        int j=0;
        while(j<=n && a[j].first-a[i].first<=now) //x坐标在指定区域  
            j++;
        j--;
        if (j-i+1=l && a[u].second<=r)
                    ans++;
            if (ans>=c)
                return true; 
        }
    }
    return false;
}
int main()
{
    cin>>c>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].first>>a[i].second;
    sort(a+1,a+1+n);//按照x坐标从小到大的顺序排列,x相同时按照由y坐标从小到大的方式排序
    int l=0,r=10000;
    while(l>1;
        if (check(mid-1))
            r=mid;
        else
            l=mid+1;
    }
    cout< 

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/312127.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号