二分查找判断是否合法设置的bool函数,请问定义int类型的数字有什么用啊?谢谢!
4条回答 默认 最新
- StjpStjp 2021-08-25 09:32关注
如果我的回答对你有帮助,请点击采纳按钮,谢谢
思路:
首先我们输入 n 和 k 并且运用二分找到合适的尺寸,而l 必须要足够小,r 必须要足够的大。题中写道数组中的数最大不会超过 100000000 ,所以我们设 100000001 就可以了。现在就走到了判断的环节,我们如何判断 mid 是太小还是太大呢?我们需要编写一个新函数 -- f。
在函数 f 中,我们依次要判断 a 中的每一个数并计算出能切出多少个 mid ,还要用一个变量 ans 储存他们,如果 ans 分的分数比 k 多或者正好等于,返回真。如果是小于 k ,返回假。
当 f 返回的是真的时候,我们就要试试还能不能把 mid 调大一点,就要
l = mid;
如果返回的是假,我们就加的太大了,就要把 midmid 调小一点,就要r = mid;
一直到结束,输出 l 就可以了。完整代码区:
#include <bits/stdc++.h> #include <queue> #include <stack> #include <cmath> #include <string> #include <cstdio> #include <iomanip> #include <cstring> #include <cstring> #include <iostream> #include <algorithm> using namespace std; long long n, k; long long a[1000005]; bool f(long long x) { long long ans = 0; for (int i = 1; i <= n; i++) { ans += a[i] / x; } return ans >= k; } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; long long l = 0, r = 100000001; long long mid; while (l + 1 < r) { mid = (l + r) / 2; if (f(mid)) l = mid; else r = mid; } cout << l << endl; return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 使用ue5插件narrative时如何切换关卡也保存叙事任务记录
- ¥20 软件测试决策法疑问求解答
- ¥15 win11 23H2删除推荐的项目,支持注册表等
- ¥15 matlab 用yalmip搭建模型,cplex求解,线性化处理的方法
- ¥15 qt6.6.3 基于百度云的语音识别 不会改
- ¥15 关于#目标检测#的问题:大概就是类似后台自动检测某下架商品的库存,在他监测到该商品上架并且可以购买的瞬间点击立即购买下单
- ¥15 神经网络怎么把隐含层变量融合到损失函数中?
- ¥15 lingo18勾选global solver求解使用的算法
- ¥15 全部备份安卓app数据包括密码,可以复制到另一手机上运行
- ¥20 测距传感器数据手册i2c