文章
10
粉丝
66
获赞
3
访问
45.3k
解析:
题目大意:有一根木棒,不断把它掰断形成新的木棒,每次只取其中一根掰成两部分,所有的木棒长度都是正整数,并且这些木棒中最短者长度的两倍始终大于最长的,问最多可以掰成多少根木棒(第一判断标准),并且最长木棒与最短木棒的长度之差最小(第二判断标准)。
要用DFS进行搜索,维护一个木棒长度列表以及这中间的最大值和最小值。最暴力的做法是,每次取出某一根木棒,试探着掰成两部分再加入长度列表,更新最大值和最小值并看看是否满足条件,如此反复直到不能掰断为止。当然,这样可能会超时。
在某个掰断的过程中,设选取的木棒长度为L,新掰成的两根木棒长度分别为L1和L2,且L1 ≤ L2,实际上,为了满足题目条件,只需要取出最长的木棒掰开,并且L1一定满足⌊L/3⌋+1 ≤ L1 ≤ ⌊L/2⌋,L1一定是所有木棒中最短的。
L1 ≤ ⌊L/2⌋很容易理解,下面先证明每次只需要取最长的木棒掰开:
证明:假设长度列表中最大值为max,最小值为min,由题意有min×2>max。假如取的不是最长的木棒,所取木棒最大长度为Lm=max-1,那么掰开后较短的部分最长也只有⌊(max-1)/2⌋<min,违反了题设条件。所以只能取最长的木棒。
接下来证明L1 ≥ ⌊L/3⌋+1:
证明:1、假设L能被3整除,设L/3=k,k为正整数。假如将木棒掰成L1=k和L2=2k,就违反了条件。随着L1减少,L2会增大,条件依然不成立。而掰成L1=k+1与L2=2k-1,2(k+1)>2k-1恒成立,同样L1增大会使得L2减小,条件依然满足。
2、假设L不能被3整除,先考虑L ≥ 4的情况,设⌊L/3⌋=k,k为正整数。假如将木棒掰成L1=k和L2=L-k,由3k<L得2k<L-k,违反了条件。随着L1减少,L2会增大,条件依然不成立。而掰成L1=k+1与L2=L-k-1,由k+1>L/3得2(k+1)>L-k-1恒成立,同样L1增大会使得L2减小,条件依然满足。再考虑L=...
登录后发布评论
暂无评论,来抢沙发