博客

Q04切分木棒

题目

假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段，但是 1 根木棒只能由 1 人切分，当木棒被切分为 3 段后，可以同时由 3 个人分别切分木棒（图 2）。

求最多有 m 个人时，最少要切分几次。譬如 n ＝ 8，m＝ 3 时如图所示，切分 4 次就可以了。

当 n ＝ 20， m ＝ 3 时的最少切分次数为 _____ ；当 n ＝ 100， m ＝ 5 时的最少切分次数为 _____ 。

答案：8、22

代码

#include <bits/stdc++.h>
using namespace std;

int helper(int n,int m){
	priority_queue<int> pq;
	if (n == 1) return 0;
	pq.push(n);
	int step = 0;
	while (!pq.empty()){
		int size = pq.size();
		vector<int> temp;
		for (int i = 0;i < min(m,size);++i){
			int cur = pq.top();
			pq.pop();
			temp.push_back(cur);
		}
		for (int i = 0;i < (int)temp.size();++i){
			int num1 = temp[i] / 2;
			int num2 = temp[i] - num1;
			if (num1 > 1) pq.push(num1);
			if (num2 > 1) pq.push(num2);
		}
		++step;
	}
	return step;
}

int main(void){
	int ans = helper(100,5);
	cout << ans << endl;

	return 0;
}

思路分析

1.每次都选最长的木棒进行切分，可以使尽量多的人不空闲。使用优先队列进行维护。

2.每次切分木棒时尽量均分木棒，保证最少的切分次数。

3.使用广度优先搜索比较合适，适合逐层遍历。

注意

将每轮需要切分的木棒从优先队列中弹出，存放到临时数组中去，避免一轮中多次选中同一根原始木棒。

出处

作者：图灵教育

链接：https://leetcode-cn.com/leetbook/read/interesting-algorithm-puzzles-for-programmers/90ach5/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。