2020 蓝桥杯大学模拟赛(三) - 程序设计:分披萨题解 电玩女神 2022-12-28 14:15 147阅读 0赞 ### 文章目录 ### * 题目描述 * * 输入格式 * 输出格式 * 数据范围 * 样例输入 * 样例输出 * 算法分析 * 解题代码 -------------------- # 题目描述 # 由于太久没有⻅到朋友们,⼩明这天晚上做了⼀个甜美的梦。 这天⼀共有`n`个同学⼀起聚餐,他们⼀共点了`m`块披萨,每块披萨的⼤⼩不尽相同,分别为 **ai** 。 现在遇到了⼀个尴尬的问题,由于⼩明是⼀个正直的⼈,他希望在场的所有⼈分得的披萨⼀样⼤, 但披萨只能被切成整数⼤⼩,不同的披萨之间也不能拼接。现在他想知道,每个⼈最多能吃到多⼤ 的披萨呢。 ## 输入格式 ## > 第⼀⾏包含两个整数 , 表示有 `n` 个同学和 `m` 块披萨。 > 接下来⼀⾏ `m` 个数表示每块披萨的⼤⼩。 ## 输出格式 ## > 输出⼀⾏,每个⼈最多能吃到多⼤的披萨。 ## 数据范围 ## ![1][] ## 样例输入 ## 4 2 7 9 ## 样例输出 ## 3 # 算法分析 # 这道题思维需要转化一下,如果按照一般贪心的想法,将每种披萨都对于每一个同学平分,这样可以保证公平性,每个同学都分到一样大的披萨,但是这种方法得出的最大披萨数是不正确的。 因为每种披萨是不能拼接的,也就意味着考虑每个人吃到的披萨都是某一种披萨的最大。 **那怎么保证某一种披萨的最大呢。** 我们换个思维,先保证某一种披萨的最大值,再保证每个同学的公平性。 那么就可以使用二分的思想,二分披萨的最大值,然后去验证在这个披萨的最大值下,能不能保证公平性,使得每个同学都能分到这么大的披萨 # 解题代码 # #include <iostream> using namespace std; int pizze[100005]; int n,m; bool check(int mid) { //验证在当前披萨大小下,能否给每个同学都分到这么大 int temp = 0; //记录当前大小下,能分给多少个同学 for(int i = 0; i < m; i++) temp += pizze[i] / mid; if(temp >= n) return true; else return false; } int main() { cin >> n >> m; for(int i = 0; i < m; i++) cin >> pizze[i]; //二分披萨的最大值的大小 int l = 0, r = 1000005; int mid = 0; while(l <= r){ int mid = (l + r) >> 1; if(check(mid)) l = mid + 1; else r = mid - 1; } cout << r << endl; return 0; } [1]: /images/20221120/7644d29feeff4c0ba7cf29de4e4ded20.png
相关 【题解】计蒜客 2020 蓝桥杯大学 B 组省赛模拟赛(一) 试题目录 A. 结果填空:有趣的数字(签到) B. 结果填空:爬楼梯(dp) C. 结果填空:七巧板(数论) D. 结果填空:苹果(贪心) 落日映苍穹つ/ 2023年07月01日 03:24/ 0 赞/ 9 阅读
相关 2020 蓝桥杯大学模拟赛(三) - 程序设计:突破障碍题解 文章目录 题目描述 输入描述 输出描述 数据范围 样例输入 样例输出 算法分析 解题 蔚落/ 2022年12月28日 14:15/ 0 赞/ 120 阅读
相关 2020 蓝桥杯大学模拟赛(三) - 程序设计:养猫题解 文章目录 题目描述 输入格式 输出格式 数据范围 样例输入 样例输出 算法分析 解题 素颜马尾好姑娘i/ 2022年12月28日 14:15/ 0 赞/ 154 阅读
相关 2020 蓝桥杯大学模拟赛(三) - 程序设计:分披萨题解 文章目录 题目描述 输入格式 输出格式 数据范围 样例输入 样例输出 算法分析 解题 电玩女神/ 2022年12月28日 14:15/ 0 赞/ 148 阅读
相关 蓝桥杯大学模拟赛(二) - 程序设计:植物大战僵尸题解 文章目录 题目描述 输入描述 输出描述 数据范围 输入 输出 算法分析 算法过程 - 日理万妓/ 2022年12月28日 14:15/ 0 赞/ 153 阅读
相关 2020 蓝桥杯大学模拟赛(二) - 结果填空:迷宫题解 文章目录 题目描述 输入 算法分析 方法一: 如何解决并发性问题呢? 方法二: 电玩女神/ 2022年12月28日 14:15/ 0 赞/ 121 阅读
相关 2020蓝桥杯省赛模拟赛 目录 第一题: 第二题: 第三题: 第四题: 第五题: 第六题: 第七题: 第八题: 第九题: 第十题: 电玩女神/ 2022年12月13日 11:27/ 0 赞/ 204 阅读
相关 蓝桥杯模拟赛:猜算式 你一定还记得小学学习过的乘法计算过程,比如: 请你观察如下的乘法算式 ![这里写图片描述][SouthEast] 星号代表某位数字,注意这些星号中, 0~9中的每个数 Myth丶恋晨/ 2022年06月18日 09:48/ 0 赞/ 272 阅读
还没有评论,来说两句吧...