1033赶牛入圈题解
AC算法O($n^2logn$)
首先通过提示我们可以知道,这道题目需要用 二分,前缀和,离散化来解决。
二分
众所周知,正方形边长越大,其中包含的三叶草越多,所以我们可以再1-10000的范围内二分答案。
离散化
再者,本道题目坐标范围为1-10000,如果死开数组会爆掉,又因为三叶草数量做多只有500,所以我们可以离散化,用一个1000*1000的数组来存。离散化不懂得看这里。
判断
每当二分到一个边长$mid$时,我们如何判断这个边长合不合法呢?我们可以用类似于尺取法的方法来判断:
假设现在1000*1000的离散化数组横坐标上存储的其中一段的离散化前的数字为:
$…,x_{i-2},x_{i-1},x_{i},x_{i+1},x_{i+2},…$
其中$x_{i+1}-x_{i-2} \le mid < x_{i+2}-x_{i-2}$
这意味着,在离散花化前的真正的土地上,$x_{i+1}-x_{i+2}$是没有三叶草的,当我们选取$x_{i-2}-x_{i+1}$的土地时,就相当于选取$x_{i-2}~-~x_{i-2}+mid$的土地,他们是相互等价,相互可以转化的。
我们在横坐标、纵坐标上选取所有小于$mid$的最大区间,将这些横、纵坐标上的区间依次配对,当其中一个配对的三叶草数量大于$c$时,返回正确;如果所有的配对都无法满足,返回错误。具体看这段代码巨佬们请回避:
bool check(int len){
for(int x1=1,x2=1;x2<=num[0];x2++){//尺取横坐标
while(num[x2]+1-num[x1]>len) x1++;
for(int y1=1,y2=1;y2<=num[0];y2++){//尺取纵坐标
while(num[y2]+1-num[y1]>len) y1++;
if((sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1])>=c)//sum代表二维前缀和,下文讲
return true;
}
}
return false;
}
虽然有$x1,x2,y1,y2$四个变量,但是仔细观察发现他们都从1升到1000,时间复杂度只有$O(n^2)$,绰绰有余了。
二维前缀和
二维前缀和可以在$O(1)$的时间内判断某个矩形内的三叶草数量,这也是上文中时间复杂度只有$O(n^2)$的原因。具体的计算方法大家都懂,本人就不在赘述,请看状态转移方程:
$sum_{i,y}=a_{i,y}+sum_{i,y-1}+sum_{i-1,y}-sum_{i-1,y-1}$
题目就讲到这里,具体的需要大家去摸索。
讲解者:方彦哲
Fesdrer
谢谢观看!!!