题意分析
小Hi和小Ho有一个存储箱,这个存储箱是一个高度为H的圆台形,上宽下窄,其中底部的半径为R,顶部的半径为R+H。
小Ho这一天买了N张唱片回来,每张唱片都是高度为1的圆柱形,且都拥有与其他唱片不同的半径。小Ho希望能将这些唱片放进储存箱中(现在还是空的),但是为了不受到小Hi莫名其妙的责罚,他定下了如下的放置规则。
1.每张唱片都必须水平放置,且其圆心与储存箱的圆心在垂直方向上重合。
2.每张唱片要么放置在储存箱的底部,要么放置在另一张唱片的上方,不能凌空卡在储存箱的某一个位置。
3.相邻的两张唱片,上方唱片的半径减去下方唱片的半径的值应当不超过M。 需要注意的是,上方唱片的半径小于下方唱片的半径也是允许的。虽然题目描述里没有明确说明,但是通过样例数据我们可以推测出这一点,否则样例输出不会是4。
现在小Ho希望能够计算出,他最多能将多少张唱片放入存储箱中。
算法分析
由于存储箱是梯形的,越到上面越宽,所以我们应该尽量把半径小的唱片放在下面。
因此我们先对所有的唱片进行排序,按照半径的长度,将半径小的唱片排在前面,记作r[1..N]
。
然后考虑将唱片一张一张放入存储箱。
假设现在我们正在放置r[i]
,此时已经放置了S
张唱片:
- 若
r[i] > R+S
,则表示该唱片无法放入存储箱。之后的唱片都比r[i]
要大,所以一定无法放入。因此我们最多能够放置的唱片数即为min(S, H)
。 - 若
r[i] ≤ R+S
,则表示该唱片可以放入存储箱,则S = S+1
。
其伪代码为:
S = 0
for i = 1 .. N
if (r[i] > R + S)
break;
else
S = S + 1;
end if
end for
ans = min(S, H)
但是在这个算法中我们少考虑了一个条件:相邻的两张唱片,上方唱片的半径减去下方唱片的半径的值应当不超过M,因此它是不正确的。
我们重新来观察已经排好序的r
数组,假设只存在一个i
,有r[i] + M < r[i + 1]
。
此时我们可以将r
数组分成两段:r[1..i]
和r[i+1..N]
。每一段段内的唱片都是可以连续放置的。
对于这种情况,我们可以把r[1..i]
这一段放在r[i+1..N]
上面,即从下往上依次放置:r[i+1], r[i+2], ... r[N], r[1], r[2], ... r[i]
举个例子:
N = 5, R = 10, H = 5, M = 1。
r = [1,2,4,5,6]
则 r 分为 [1,2]
和 [4,5,6]
两段。我们可以把[1,2]
放在 [4,5,6]
上面,从下往上依次:4, 5, 6, 1, 2
。
总的最大放置唱片数为5
。
从这个例子中,我们可以知道,若存在r[i] + M < r[i + 1]
,就表示需要进行分段。直到某一段中的某一张唱片“卡住”(r[k] > R + S
),这时对于r[1]...r[k-1]我们可以用上述放置方法全部放进存储箱里。而对于r[k]...r[N]实际上没有任何方法能放进存储箱里。
举个例子:
N = 10, R = 10, H = 5, M = 2。
r = [1,2,5,6,9,11,12,14,17,18]
则 r 分为 [1,2]
[5,6]
[9,11,12,14]
[17,18]
四段,其中半径为14的唱片会“卡住”。这时我们可以将半径小于14的唱片按从下到上:9, 11, 12, 5, 6, 1, 2
的顺序放进存储箱。而半径14及以上的唱片实际上没有任何方法能放进存储箱里(证明留给coders思考)。
综上所述,最优的放置方法可以把没“卡住”的唱片全部放进存储箱。我们可以先将 r 分段,依次对每一段检查会不会出现“卡住”的唱片。
或者也可以使用一个简单的处理办法:每次遇到r[i] + M < r[i + 1]
的情况时,将S
重置为0
。
改进后的伪代码为:
S = 0
ans = min(h, N)
for i = 1 .. N
if (i > 1 && r[i] - r[i - 1] > M)
S = 0;
endif
if (r[i] > R + S)
ans = min(i - 1, H);
break;
endif
S = S + 1
end for
return ans
排序的时间复杂度为 O(NlogN),计算结果的时间复杂度为 O(N),总的时间复杂度为 O(NlogN)。
楼主你先告诉我你AC了没?
同问
这能过吗?样例好像都过不了啊!