Acwing-121-赶牛入圈(二分, 二维前缀和,离散化)

2021-02-04 06:14

阅读：397

标签：print 链接建立二维 include 题意 int 离散化 name

链接:

https://www.acwing.com/problem/content/123/

题意:

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

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

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

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

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

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

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

思路:

离散化之后搞一下二维前缀和.再查询就可以降到500^2*log(1000)左右.

代码:

#include 
using namespace std;

struct Node
{
    int x, y;
    int node;
}node[510];
int Map[10000][10000];
int Number[2010];
int c, n, pos;

bool Check(int len)
{
    for (int x1 = 1, x2 = 1;x2  len)
            x1++;
        for (int y1 = 1, y2 = 1;y2  len)
                y1++;
            if (Map[x2][y2]-Map[x2][y1-1]-Map[x1-1][y2]+Map[x1-1][y1-1] >= c)
                return true;
        }
    }
    return false;
}

int main()
{
    scanf("%d %d", &c, &n);
    int x, y;
    pos = 0;
    for (int i = 1;i

Acwing-121-赶牛入圈(二分, 二维前缀和,离散化)

标签：print 链接建立二维 include 题意 int 离散化 name

原文地址：https://www.cnblogs.com/YDDDD/p/11479835.html

上一篇：windows 上git安装及gitlab 连接

下一篇：【Windows Server存储】windows文件系统

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Acwing-121-赶牛入圈(二分, 二维前缀和,离散化)
文章链接：http://soscw.com/index.php/essay/50764.html

亲，登录后才可以留言！

Acwing-121-赶牛入圈(二分, 二维前缀和,离散化)

链接:

题意:

思路:

代码:

评论

热门文章

推荐文章

最新文章

置顶文章