| 【备战秋招】每日一题:4月15日美团春招第二题:题面+题目思路 + C++/python/js/Go/java带注释 | 您所在的位置：网站首页 › 美团分练 › 【备战秋招】每日一题:4月15日美团春招第二题:题面+题目思路 + C++/python/js/Go/java带注释 |
【备战秋招】每日一题:4月15日美团春招第二题:题面+题目思路 + C++/python/js/Go/java带注释
|
为了更好的阅读体检，为了更好的阅读体检，，可以查看我的算法学习博客第二题-分糖果 在线评测链接:P1236 题目内容某天，塔子哥去商店买了两种不同口味的糖果，分别买了 a 个和 b 个。当他回到家时，他发现他需要将这些糖果分配给班上的 n 个小朋友，以确保每块糖果都得恰好分到一个小朋友，而且不能有任何浪费。 塔子哥知道，如果两种糖果混在一起吃，那么它们的味道就不是很好，因此每个小朋友只能得到其中一种糖果。此外，塔子哥希望尽可能让每个小朋友都能够得到尽可能多的糖果，而且他希望分得最少糖果的小朋友也能得到尽可能多的糖果。 为了实现这个目标，塔子哥决定请你来帮他编写一段程序来帮助他计算出最少糖果的小朋友最多能获得多少糖果，你能帮帮他吗？ 输入描述第一行一个正整数 T ，表示有 T 组数据。 对于每一组数据，输入一行 n , a , b ，中间用空格隔开。
对于每一组数据，输出仅一行一个整数，表示答案。 样例输入 2 5 2 3 4 7 10输出 1 3样例解释 第一组数据，每个小朋友都恰好分得一个糖果 第二组数据，可以分成: (3个第一种，4个第一种，5个第二种，5个第二种)，这样第一个小朋友分得最少，没有其他方案使得分得最少的那个小朋友的糖果数量更大。 思路 二分答案 常识一般最小化最大，最大化最小的问题，都是二分答案来解决。 正确性分给一个孩子的糖果越多，则分到糖果的孩子就越少。 分给一个孩子的糖果越少，则分到糖果的孩子就越多。 故答案具有二段性，可以二分。 做法二分最终拿到的糖果的最少个数（即答案）为 mid，然后 check 函数是考虑对于每个孩子分到 mid 个糖果，最多可以分给多少个孩子,设为x=a / mid + b / mid。 那么只要x \geq n ，mid就可行。 时间复杂度：x的求解可以O(1)直接计算 , 那么复杂度即 O(\log (\max(a,b))) 类似题目推荐这是一道比较简单的二分答案题。这里给大家推荐一些二分答案的题目 LeetCode 1.LeetCode 875. 爱吃香蕉的珂珂 2.LeetCode 2187. 完成旅途的最少时间 3.LeetCode 6325. 修车的最少时间 4.LeetCode 2226. 每个小孩最多能分到多少糖果 Codefun2000 P1189. 华为实习 2023.04.12-实习笔试-第一题-购物系统的降级策略 P1106. 腾讯音乐 2023.3.23-第二题-划分字符串 P1006. 华为秋招 2022.9.21-数组取min P1093. 米哈游 2023.03.19-第三题-塔子哥的无限字符串 - 难度较大 代码 CPP #include // 引入标准库头文件 using namespace std; int main() { // 主函数开始 int T; // 定义一个变量T，表示测试用例数量 cin >> T; // 读入测试用例数量 while (T--) { // 循环处理每个测试用例 int n, a, b; // 定义变量n、a、b cin >> n >> a >> b; // 读入变量n、a、b的值 int l = 0, r = max(a, b); // 二分答案 while (l < r) { int mid = (l + r + 1) >> 1; // 如果最多能发的人数多于n,则收缩左端点 if (a / mid + b / mid >= n) l = mid; else r = mid - 1; // 否则移动右端点 } cout > 1; // 如果最多能发的人数多于n,则收缩左端点 if (a / mid + b / mid >= n) l = mid; else r = mid - 1; // 否则移动右端点 } System.out.println(l); } } } Python T = int(input()) while T > 0: n, a, b = list(map(int, input().split())) def check(cnt): return a // cnt + b // cnt >= n l, r = 0, max(a, b) #二分答案 while l < r: mid = (l + r + 1) >> 1 #如果最多能发的人数多于n,则收缩左端点 if check(mid): l = mid else:# 否则移动右端点 r = mid - 1 print(l) T -= 1 Go // 最大化最小值 ---> 二分答案 package main import( "fmt" ) func main(){ var t int fmt.Scanln(&t) for i := 0 ; i < t ; i++{ var n int var a int var b int fmt.Scanf("%d %d %d\n", &n, &a, &b) ans := getResult(n, a, b) fmt.Println(ans) } } // 二分答案 func getResult(n, a, b int) int{ l := 1 r := 10001 for l < r{ mid := (l + r) / 2 if check(n, a, b, mid){ l = mid + 1 }else{ r = mid } } return l - 1 } // 判断合法性 func check(n, a, b, mid int) bool{ // ans 计算 最多能分给多少个小孩 ans := 0 ans += a / mid ans += b / mid return ans >= n } Js const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () => (await iter.next()).value; async function main() { let t = parseInt((await readline())) while (t--) { const input = (await readline()).split(" ").map(Number) const n = input[0], a = input[1], b = input[2] let l = 1, r = 20000; const check = m => { const na = Math.floor(a / m); const nb = Math.floor(b / m); return (na + nb >= n); }; // 二分答案 while (l |
【本文地址】