华华给月月准备礼物题解
华华给月月准备礼物
https://ac.nowcoder.com/acm/problem/23049
很典型的一个二分求解题。
理解题意后我们会发现，我们只需要找到一个长度，让每一根棍子可以锯出这种长的的总个数大于等于想要获得的棍子个数即可。
所以我们可以在长度为1和我们所拥有的棍子中最长的那根棍子的长度之间进行二分。
先把num[]数组排序，如果可以获得的大于等于k的话就记录这个长度，然后往右找，小于k的话就往左找。
最后输出max即可，代码如下。
import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
public static void main(String args[])throws IOException
{
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int n = (int)in.nval;
in.nextToken();
int k = (int)in.nval;
int num[] = new int[n];
for(int t=0;t<n;t++)
{
in.nextToken();
num[t] = (int)in.nval;
}
int sum=0;
Arrays.sort(num);
int l=1,r=num[n-1],mid=(l+r)>>1,max=0;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid,num)>=k)
{
max = Math.max(max,mid);
l = mid+1;
}
else{
r = mid-1;
}
}
out.print(max);
out.flush();
}
public static int check(int p,int num[])
{
int sum=0;
for(int i=0;i<num.length;i++)
{
sum+=(num[i]/p);
}
return sum;
}
}
查看11道真题和解析