专栏文章

题解：P12269 [蓝桥杯 2024 国 Python B] 切木棒

kkuaiCreator
P12269题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipj7z0f
此快照首次捕获于
2025/12/03 12:53
3 个月前
此快照最后确认于
2025/12/03 12:53
3 个月前
查看原文

解题思路

看到求最大值最小，考虑二分答案。
切割次数越多，则最长的木棍长度可以越短，具备单调性。二分答案的思路可行。
因此二分最长木棍的长度 dd，验证时对于原第 ii 根长度为 lil_i 的木棍，需要切割的次数为 lid\Large\frac{l_i}{d}，但是若 d∣lid\mid l_i 说明 dd 能够整除 lil_i 那么少切一次，因为刚好整除时，最后一刀切在木棍边缘。
C
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int n, m, l[N];
bool check(int mid) {
	int cut = 0;
	for (int i = 1; i <= n; i++) {
		cut += l[i] / mid;
  		if (l[i] % mid == 0) cut--; //重点：能整除的话少切一次
	}
	return cut <= m;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> l[i];
	int l = 1, r = 1e9, ans;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	cout << ans;
  return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...