二分算法分金块c++
时间: 2025-01-11 12:32:11 浏览: 5
C++ 实现二分算法进行金块分配
为了实现基于二分法的金块分配问题,可以采用如下方法。该方案利用了C++中的lower_bound()
函数来简化二分查找过程。
函数定义与初始化
首先,定义一个辅助函数用于判断当前尝试的最大重量是否满足条件:
#include <vector>
using namespace std;
// 判断能否在给定最大重量limit下完成分配
bool canDistribute(const vector<int>& weights, int limit, int people) {
int count = 0;
int currentWeight = 0;
for (int weight : weights) {
if (currentWeight + weight > limit) { // 当前组超重则新开一组
++count;
currentWeight = 0;
}
currentWeight += weight;
}
// 处理最后一组未计入的情况
if (currentWeight != 0) {
++count;
}
return count <= people; // 组数不超过人数即为可行
}
此部分逻辑实现了对于特定限重条件下验证是否存在合法分配方案的功能[^2]。
主体逻辑构建
接下来,在主程序中通过调用上述辅助函数并结合二分查找技术求得最小可能的最大单次搬运量:
pair<int, bool> binarySearchForMinLimit(vector<int>& weights, int k) {
int low = *max_element(weights.begin(), weights.end()); // 至少要能搬动最重的那个金块
int high = accumulate(weights.begin(), weights.end(), 0); // 极端情况下一个人把所有金块都搬走
while (low < high) {
int mid = low + (high - low) / 2;
if (!canDistribute(weights, mid, k)) {
low = mid + 1;
} else {
high = mid;
}
}
return make_pair(low, canDistribute(weights, low, k));
}
这里采用了经典的二分搜索框架,不断调整上下界直至找到最优解。值得注意的是初始区间的设定:最低限度应当不低于任何一个单独金块的质量;而理论上最高值则是全部金块总质量之和。
完整示例代码展示
最后给出完整的可执行版本供参考学习:
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
/// ... 上述两个函数的具体实现 ...
int main() {
int n, k;
cin >> n >> k;
vector<int> goldWeights(n);
for(int i = 0 ;i<n;i++){
scanf("%d", &goldWeights[i]);
}
auto result = binarySearchForMinLimit(goldWeights, k);
cout << "Minimum possible maximum load per person is: " << result.first << endl;
cout << "Is this distribution feasible? " << (result.second ? "Yes" : "No") << endl;
return 0;
}
这段代码展示了如何接收用户输入的数据集以及最终输出计算得到的结果。整个流程清晰明了易于理解[^4]。