POJ(PKU) 2976 Dropping tests

普通に平均最大化をする。

小数の闇を見た。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <iostream>
#include <math.h>

using namespace std;

int n,k,d[1002][2];

double t[1002];

bool ch(double x){

  
  for(int i = 0;i < n;i++){
    t[i] = 100.00 * d[i][0] - x * d[i][1];
  }
  
  sort(t,t + n,greater<double>());
 double a = 0;
  
  for(int i = 0;i < n - k;i++){
    a += t[i];
  }
  
  return a >= 0;
}


int main(){
  
  while(1){
  
  scanf("%d%d",&n,&k);
  if(n == 0)break;
  for(int i = 0;i < n;i++){
    scanf("%d",&d[i][0]);
  }
  for(int i = 0;i < n;i++){
    scanf("%d",&d[i][1]);
  }
  
  double lb = -1,ub = 101;

  for(int i = 0;i < 100;i++){
    double mid = (lb + ub) / 2;
    if(ch(mid)) lb = mid;
    else ub  = mid;
  }

  printf("%d\n", (int)floor(lb + 0.5));
  }
  return 0;
}