Angry Cows

GDKOI 2016期间,朱轩宇在地铁上问了我Angry Cow B,并告诉了我题解。后来在佛山的时候看到了原题,但没想起来。

Angry Cow A

数轴上的一些点上有草堆,发射奶牛到草堆上会爆炸,范围(半径)为1。受到半径为n的爆炸的攻击的草堆会立刻引发半径为n+1的爆炸,且炸完就消失不再爆炸。已知草堆位置,求发射一头奶牛最多炸几个草堆?

我的第一思路:用邻接链表储存每两点间距离,然后排序,用距离作为关键字。然后暴搜,时间复杂度O(n2)O(n^2)

到了上课时才发现,是“数轴”而不是“坐标轴”!我错以为是二维的问题了,一维还不简单!

题解:

for each 草堆:
    explode to the left;
    explode to the right;
    max_explode=max(max_explode,right-left);

Angry Cow B

数轴上有若干草堆,发射奶牛到草堆上会爆炸,半径为R(未知)。要使所有草堆爆炸,只有n头奶牛(已知),R至少为多少?

题解:二分+贪心。二分半径,算出所需要奶牛数量,与n比较。

因为x[0]是注定要毁灭的,就干脆让x[0]在一个爆炸半径的最左端,使得这个爆炸的效率最高。算出这次爆炸能炸掉多少个草堆,接着再找下一个一定要毁灭的草堆,如法炮制。这便是贪心。

Angry Cow C

数轴上有若干位置已知的草堆,发射奶牛到坐标上会立刻引爆,爆炸半径为R(未知)。受到半径为r的爆炸冲击的草堆会立刻引发半径为r-1的爆炸。求一头奶牛要炸掉所有草堆最小的R。

老师说用两层二分,但没有什么想法。第一层二分自然是二分R,第二层呢?有同学上去说,不知道我有没有听错,二分查找左端点和右端点,使得做右端点间任意一点爆炸都能分别蔓延到最右和最左端点,然后根据区间情况判断R的选择。时间复杂度O(log2Rmax2log2XmaxRcur)O(\log 2R_{max}*2\log 2X_{max}*R_{cur}),当前R并不会怎么算,但经过优化,应该不会特别大。把最坏情况带入,记得当时算了会超时,但是现在看来还好。

我的一种思路也是先二分R,后找左右端点。只是找端点的方法不太一样,我是逆向爆炸。举例:想找右端点,从左边开始以1为半径爆炸,找到半径内最右的点,扩大爆炸半径,引爆它,如此如此。即:

p=0
for r=1 to mid:
    rightend=x[p]+r;
    while x[p]<=rightend
        p++;
    p--;

那么rightend就会得到右端点。这个的时间复杂组为O(log2Rmax2Rcur)O(\log 2R_{max}*2*R_{cur}),好像会快一点。

老师没有公布题解,或我没有认真听,但老师给了一个启发式的算法:DP。f[i]储存炸掉前i个点所需半径R。但是状态转移方程比较不好处理。

avatar
Kerry Su