首页 > 试题广场 >

华华给月月准备礼物

[编程题]华华给月月准备礼物

热度指数：22 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为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

输出

备注:

，，

算法知识视频讲解

sunrise__sunrise

发表于 2020-04-16 16:51:23

华华给月月准备礼物 Solution 根据题目大意，很快可以发现，如果我们枚举一个，可以在这个情况下求到根木棍，我们就希望能不能再求更大的；否则，可行解一定比当前ans更小。符合单调特性，采取二分的思路。再说说我对二分的心得二分大致可以分为两种思路，范围缩小让逼近答案 while (l 展开全文

肖战公关团队

发表于 2020-04-23 17:30:08

Solution 看完题目就能想到这个题也许可以二分答案。但是需要知道这个题目的答案可不可以满足单调性。即对于所有满足条件，则也满足条件。很显然这是满足单调性的，如果满足条件，即那么对于而言，显然有那么这个题就可以二分答案了。还有一个点是答案可能会到。于是二分范围直接是区间即可。本题ch 展开全文

shyyhs

发表于 2021-01-13 15:49:38

前言: 真就一眼题. 思路: 二分即可. 代码: #include <bit.stdc++.h> using namespace std; const int N=2e5+50; int w[N],n,m; bool check(int len) { int sum=0; 展开全文

一只橘橘猫

发表于 2020-04-16 12:34:19

题意：解法：：POJ 3273-Monthly Expense ：POJ 3122-Pie 时间复杂度： std: #include <bits/stdc++.h> using namespace std; #define ll long long const int maxn 展开全文

ziuch

发表于 2020-08-24 15:39:21

题目描述二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度展开全文

Kur1su

发表于 2020-04-16 11:23:29

Solution 分析一下题目, 这道题我们首先分析能不能二分二分的条件是满足单调性和 check答案比较简单这道题目我们可以二分长度, 显然是满足单调性的每次二分木棍的长度mid, 然后对每个a[i] 都能得到 a[i] / mid 个需要的木棍我们check一下能不能得到超过k个所需木棍直接统展开全文