华华给月月准备礼物

NC23049. 华华给月月准备礼物

描述

二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。
华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？

输入描述

第一行两个正整数N、K，表示木棍原本的根数和华华希望得到的木棍根数。
第二行N个正整数表示每根木棍的初始长度。

输出描述

输出一行一个非负整数，表示华华最终得到的n根木棍的每根最大长度。

示例1

输入:

5 10
4 4 4 5 3

输出:

说明:

如果长度为2，只能得到2+2+2+2+1=9根，不够；长度为1可以得到4+4+4+5+3=20根，足够。所以答案最大是1。

示例2

输入:

5 3
1 2 3 4 5

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

Java 解法, 执行用时: 586ms, 内存消耗: 21820K, 提交时间: 2023-08-12 10:24:12

import java.util.Scanner;
public class Main {
    static int n,k;
    static int []list=new int[200001];
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        k=scanner.nextInt();
        for(int i=0;i<n;i++){
            list[i]=scanner.nextInt();
        }
        int l=0,r=(int)1e9;
        while(l<r){
            int mid=(l+r+1)/2;
            if(check1(mid))l=mid;
            else r=mid-1;
        }
        System.out.println(l);
    }

    private static boolean check1(int mid) {
        long res=0;
        for(int i=0;i<n;i++) res+=list[i]/mid;
        if(res>=k)return true;
        return false;
    }
}

Python3 解法, 执行用时: 337ms, 内存消耗: 17204K, 提交时间: 2023-08-12 10:23:36

n, k = map(int, input().split())
lst = list(map(int, input().split()))
li = 1
r = max(lst) + 1
while li < r:
    m = (li + r) // 2
    if sum([i//m for i in lst]) >= k:
        li = m + 1
    else:
        r = m
print(li - 1)