二分答案——洛谷P2440木材加工

题目描述
问题分析
这个题目是一类典型的二分答案问题，题目中给出我们需要将给定的长度切割成相应的K段，并且保证切割的小段的最大长度，那么我们怎么做呢，必然是在一定的区间枚举出来该切成多少才能满足切成k段并且保证长度最大，其实这里我们可以考虑二分的思想，比方说，我们最大能切的长度必然不会比原来的木头的最大的那一根还要长，并且我们确定最小可以切出1cm，若是1cm切不出便输出0.
那么二分区间的左端点l = 1, 右端点r = max({l1, l2, l3, l4…ln)
我们该怎么找呢在这个二分区间内我们就像二分查找类似的写法，在左边子区间或者右边子区间逐步逼近找出误差最小的答案，我们这时不能像二分查找对应元素那样去考虑，而是写一个check函数，我比较喜欢叫check，然后我们将每一个木头切割这个长度（向下取整）然后将可以切割的数量相加在与给定切割的数目k作为比较，如果res >= k那么证明，所切割的值偏小，那么我们应该往右区间去找，反之找左区间。

bool check(LL x) {
	LL res = 0;
	for (int i = 1; i <= n; i++) {
		res += a[i] / x;
	}
	return res >= K;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;

LL a[maxn];

int n;
LL K;
LL l = 1, r = -1;

bool check(LL x) {
	LL res = 0;
	for (int i = 1; i <= n; i++) {
		res += a[i] / x;
	}
	return res >= K;
}

int main() {
	scanf("%d%lld", &n, &K);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		r = max(r, a[i]);
	}
	LL ans = 0;
	while (l <= r) {
		LL mid = (l + r) >> 1;
		if (check(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

总结：
二分答案是在竞赛中常考的类型，其思想也是基于二分的变形，分析问题，给出以下常见题目中的关键字，判断是否使用二分。
第一类问题：
二分答案应用求解问题
求最大长度中的可能最小值是多少
问最小重量的最大值是多少

第二类问题：
最少要多少才能满足要求
在满足限制的情况下最大值是多少

对于第二类问题，我们可以抽象
对于x，有一个函数f(x)，值域为{0,1}
求满足f(x) = 0时 x的最大值

将第一类问题转换为第二类问题

对于第一类问题
我们抽象：

对于x，有一个函数f(x)
求当满足f(x) <= M时x的最大值。

二分答案——洛谷P2440木材加工

相关推荐