天天看点

poj 1064 java_poj 1064 java

题目意思就是给定N组数,求满足商的和大于等于K的最大除数R。

注意精度 注意精度 注意精度

这里可以用二分。

不用二分的算法是这样,首先求出最大的Rmax,所有数之和除以K即可,下面求出每个数“Rmax减多少就能得到更大的商”D。

给D排序,Rmax下商之和Kmin和K的差值-1就是D的下标。(差值为0时直接Rmax=R)

一些精度细节就不详细写了。。。用快排,时间复杂度O(log2n,2是底)

public class Cable_Master { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int M=1000000;//这精度xnmbyy int n=sc.nextInt(),k=sc.nextInt(); long lev[]=new long[n],max=0,dif=0,result; for(int i=0;ilev[j]){ long temp=lev[i]; lev[i]=lev[j]; lev[j]=temp; } result=dif==0?max:max-lev[(int)dif-1]; result=result