POJ1064二分

本文主要是介绍POJ1064二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

n根线，现在要把这n根线切割成k根等长（设长为len）的线，问能切得的最长的len为多少，

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.StringTokenizer;public class Main {public static void main(String[] args){new POJ1064().solve()  ; }
}class POJ1064{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final int N = 10008 ;double[] x = new double[N] ;int n , k ; boolean judge(double l){int cnt = 0 ;for(int i = 0 ; i < n ; i++){cnt += (int)(x[i] / l) ;}return cnt >= k ;}void solve(){n = in.nextInt() ;k = in.nextInt() ;double left = 0.0 , right = 0.0 , mid , res = -1 ; for(int i = 0 ; i < n ; i++){x[i] = in.nextDouble() ;right = Math.max(right , x[i]) ;}for(int i = 0 ; i < 100 ; i++){mid = (left + right) / 2 ;if(judge(mid)) res = left = mid ;else right = mid ;}out.printf("%.2f" , Math.floor(res*100)/100) ;out.println();out.flush() ; }
}class InputReader {  public BufferedReader reader;  public StringTokenizer tokenizer;  public InputReader(InputStream stream) {  reader = new BufferedReader(new InputStreamReader(stream), 32768);  tokenizer = new StringTokenizer("");  }  private void eat(String s) {  tokenizer = new StringTokenizer(s);  }  public String nextLine() {  try {  return reader.readLine();  } catch (Exception e) {  return null;  }  }  public boolean hasNext() {  while (!tokenizer.hasMoreTokens()) {  String s = nextLine();  if (s == null)  return false;  eat(s);  }  return true;  }  public String next() {  hasNext();  return tokenizer.nextToken();  }  public int nextInt() {  return Integer.parseInt(next());  }  public long nextLong() {  return Long.parseLong(next());  }  public double nextDouble() {  return Double.parseDouble(next());  }  public BigInteger nextBigInteger() {  return new BigInteger(next());  }  }  

这篇关于POJ1064二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---