【备战秋招】每日一题: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

1. P1189. 华为实习 2023.04.12-实习笔试-第一题-购物系统的降级策略

2. P1106. 腾讯音乐 2023.3.23-第二题-划分字符串

3. P1006. 华为秋招 2022.9.21-数组取min

4. P1093. 米哈游 2023.03.19-第三题-塔子哥的无限字符串 - 难度较大

代码

CPP

#include <bits/stdc++.h> // 引入标准库头文件
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 << l << "\n"; // 输出左端点
    }
} // 主函数结束

Java

import java.util.Scanner;
​
public class Main {
​
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
​
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
​
            int l = 0, r = Math.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; // 否则移动右端点
            }
​
            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 <= r) {
            const mid = Math.floor((l + r) / 2);
            if (check(mid)) l = mid+1;
            else r = mid - 1;
        }
        console.log(l-1);
        
    }
​
}
main()