文章

10

粉丝

66

获赞

3

访问

42.1k

头像
Load Balancing题解
P898 浙江大学2021年机试题
发布于2022年5月22日 12:31
阅读数 4.5k

解析:

题目大意:有一根木棒,不断把它掰断形成新的木棒,每次只取其中一根掰成两部分,所有的木棒长度都是正整数,并且这些木棒中最短者长度的两倍始终大于最长的,问最多可以掰成多少根木棒(第一判断标准),并且最长木棒与最短木棒的长度之差最小(第二判断标准)。

要用DFS进行搜索,维护一个木棒长度列表以及这中间的最大值和最小值。最暴力的做法是,每次取出某一根木棒,试探着掰成两部分再加入长度列表,更新最大值和最小值并看看是否满足条件,如此反复直到不能掰断为止。当然,这样可能会超时。

在某个掰断的过程中,设选取的木棒长度为L,新掰成的两根木棒长度分别为L1L2,且L1 ≤ L2,实际上,为了满足题目条件,只需要取出最长的木棒掰开,并且L1一定满足⌊L/3⌋+1 ≤ L1 ≤ ⌊L/2⌋,L1一定是所有木棒中最短的

L1 ≤ ⌊L/2⌋很容易理解,下面先证明每次只需要取最长的木棒掰开:

证明:假设长度列表中最大值为max,最小值为min,由题意有min×2>max。假如取的不是最长的木棒,所取木棒最大长度为Lmmax-1,那么掰开后较短的部分最长也只有⌊(max-1)/2⌋<min,违反了题设条件。所以只能取最长的木棒。

接下来证明L1 ≥ ⌊L/3⌋+1:

证明:1、假设L能被3整除,设L/3=kk为正整数。假如将木棒掰成L1kL2=2k,就违反了条件。随着L1减少,L2会增大,条件依然不成立。而掰成L1k+1与L2=2k-1,2(k+1)>2k-1恒成立,同样L1增大会使得L2减小,条件依然满足。

2、假设L不能被3整除,先考虑L ≥ 4的情况,设⌊L/3⌋=kk为正整数。假如将木棒掰成L1kL2Lk,由3kL得2kLk,违反了条件。随着L1减少,L2会增大,条件依然不成立。而掰成L1k+1与L2Lk-1,由k+1>L/3得2(k+1)>Lk-1恒成立,同样L1增大会使得L2减小,条件依然满足。再考虑L=...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发