二分查找判断是否合法设置的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 keil的map文件中Image component sizes各项意思
- ¥30 BC260Y用MQTT向阿里云发布主题消息一直错误
- ¥20 求个正点原子stm32f407开发版的贪吃蛇游戏
- ¥15 划分vlan后,链路不通了?
- ¥20 求各位懂行的人,注册表能不能看到usb使用得具体信息,干了什么,传输了什么数据
- ¥15 Vue3 大型图片数据拖动排序
- ¥15 Centos / PETGEM
- ¥15 划分vlan后不通了
- ¥20 用雷电模拟器安装百达屋apk一直闪退
- ¥15 算能科技20240506咨询(拒绝大模型回答)