思路:二分答案

常识

一般最小化最大，最大化最小的问题，都是二分答案来解决。

正确性

分给一个孩子的糖果越多，则分到糖果的孩子就越少。 分给一个孩子的糖果越少，则分到糖果的孩子就越多。

故答案具有二段性，可以二分。

做法

二分最终拿到的糖果的最少个数（即答案）为 $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-第三题-塔子哥的无限字符串 - 难度较大

代码

C++

#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()