[updated]hiho一下第72周《Disk Storage》题目分析

13
0

题意分析

小Hi和小Ho有一个存储箱,这个存储箱是一个高度为H的圆台形,上宽下窄,其中底部的半径为R,顶部的半径为R+H。

小Ho这一天买了N张唱片回来,每张唱片都是高度为1的圆柱形,且都拥有与其他唱片不同的半径。小Ho希望能将这些唱片放进储存箱中(现在还是空的),但是为了不受到小Hi莫名其妙的责罚,他定下了如下的放置规则。

1.每张唱片都必须水平放置,且其圆心与储存箱的圆心在垂直方向上重合。

2.每张唱片要么放置在储存箱的底部,要么放置在另一张唱片的上方,不能凌空卡在储存箱的某一个位置。

3.相邻的两张唱片,上方唱片的半径减去下方唱片的半径的值应当不超过M。 需要注意的是,上方唱片的半径小于下方唱片的半径也是允许的。虽然题目描述里没有明确说明,但是通过样例数据我们可以推测出这一点,否则样例输出不会是4。

现在小Ho希望能够计算出,他最多能将多少张唱片放入存储箱中。

算法分析

由于存储箱是梯形的,越到上面越宽,所以我们应该尽量把半径小的唱片放在下面。

因此我们先对所有的唱片进行排序,按照半径的长度,将半径小的唱片排在前面,记作r[1..N]

然后考虑将唱片一张一张放入存储箱。

假设现在我们正在放置r[i],此时已经放置了S张唱片:

  1. r[i] > R+S,则表示该唱片无法放入存储箱。之后的唱片都比r[i]要大,所以一定无法放入。因此我们最多能够放置的唱片数即为min(S, H)
  2. 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)

8 answer(s)

0

1 1 10 3 4 这个答案是多少

1

正确解法是把所有题意分析中的段的长度和加起来,再min(H,ans) 因为根据前面同学分析所有的短的段都可以垒在长的段上面 by 某AC

  • “所有题意分析中的段的长度和加起来”的意思是:先分段,然后将(合法的)各段的和加起来?

  • 添加评论
  • reply
0

感觉是贪心啊,每次选择符合条件的最大碟片,二叉树维护剩余碟片,nlogn

0

1.每张唱片都必须水平放置,且其圆心与储存箱的圆心在垂直方向上重合。

2.每张唱片要么放置在储存箱的底部,要么放置在另一张唱片的上方,不能凌空卡在储存箱的某一个位置。

3.相邻的两张唱片,上方唱片的半径减去下方唱片的半径的值应当不超过M。

现在小Ho希望能够计算出,他最多能将多少张唱片放入存储箱中。

请问啊。"不能凌空卡在储存箱的某一个位置"是什么意思呢??

  • 就是两张唱片必须紧挨着,中间不能留空隙~

  • 比如直接把10的卡在上面

  • 我再想为什么高度为什么不能超过H这个高度,又没有说可以不能超过H这个高度,放置条件没有说一定高度小于H

  • 谢谢各位啊,终于看懂题意了!!O(∩_∩)O哈!

  • 题目中说:Little Ho wants to put these disk into the storage。该句表明唱片必须放进唱片存储箱,不能超过高度H,根据实际情况也可知,存储箱是用来装东西的,装不下了,应该就不装了把,呵呵

  • 添加评论
  • reply
0

想问一下微软会给出标准答案么?

5

考虑Sample[1,3,4,5,10]对于M=1,采用上述算法得到最大数量放置方式为3->4->5并不会得到Sample输出

1

例子里面的[1,2,4,5,6]在容器里面放的方式从下往上应该4->5->6->1->2是合理的放置方式,结果应该是5才对

  • 正解

  • 相邻的两张唱片,上方唱片的半径减去下方唱片的半径的值应当不超过M。例子M=1。所以6->1的放置是错误的。请仔细读题

  • 题目里并没有说取得是上方唱片的半径减去下方唱片的半径的绝对值,因此1-6=-5并没有违背题意吧。

  • 同意楼上

  • 同意楼上的想法

  • 同意楼上,题目分析明显有问题,误导青少年

  • 添加评论
  • reply
1

楼主的思路是给自己加了一个条件:上面的一定要比下面大,但是原题并没有

  • 原题没有,但是可以证明在同样的条件下,小的放在下面不会差于大的放在下面

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享