text: Online JudgeProblem SetAuthorsOnline ContestsUser
  Web Board
  F.A.Qs
  Statistical Charts
  Problems
  Submit Problem
  Online Status
  Prob.ID:
  Register
  Authors ranklist
  Current Contest
  Past Contests
  Scheduled Contests
  Award Contest
  Register
  
  ## 二分WA的童鞋注意一下写法
  
  Posted by Onlynagesha at 2017-11-23 17:01:28 on Problem 3111 and last updated at 2017-11-23 17:01:39
  ```正确的写法：
  void solve()
  {
  double left = 0.0;
  double right = 0.0;
  for (int i = 0; i < N; i++)
  right = max(right, 1.0 * value[i] / weight[i]);
  
  while (1)
  {
  double mid = (left + right) / 2.0;
  for (int i = 0; i < N; i++)
  {
  item[i].idx = i + 1;
  item[i].prior = value[i] - mid * weight[i];
  }
  sort(item, item + N);
  
  double sum = 0.0;
  for (int i = 0; i < K; i++)
  sum += item[N - K + i].prior;
  
  if (sum >= 0.0)
  {
  left = mid;
  if (right - left < 1e-7)
  break; //跳出二分时需要保证运行结果是可行解
  }
  else
  right = mid;
  }
  
  sort(item + N - K, item + N, cmpIdx);
  
  for (int i = 0; i < K; i++)
  printf("%d ", item[N - K + i].idx);
  }
  
  （跳出二分时，item数组中存储的可能不是可行解）
  void solve()
  {
  double left = 0.0;
  double right = 0.0;
  for (int i = 0; i < N; i++)
  right = max(right, 1.0 * value[i] / weight[i]);
  
  while (right - left >= 1e-7)
  {
  double mid = (left + right) / 2.0;
  for (int i = 0; i < N; i++)
  {
  item[i].idx = i + 1;
  item[i].prior = value[i] - mid * weight[i];
  }
  sort(item, item + N);
  
  double sum = 0.0;
  for (int i = 0; i < K; i++)
  sum += item[N - K + i].prior;
  
  if (sum >= 0.0)
  left = mid;
  else
  right = mid;
  }
  
  sort(item + N - K, item + N, cmpIdx);
  
  for (int i = 0; i < K; i++)
  printf("%d ", item[N - K + i].idx);
  }```
  
  Followed by:
metadata: {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}