POJ(PKU) 3111 K Best

二分探索・平均最大化。
日本TLE怖い協会
もうこの問題は解きたくない。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <utility>

using namespace std;



int n,k;
int v[100010];
int w[100010];

pair<double, int> p[100012];

bool ans(double x){
  
  for(int i = 0;i < n;i++){
p[i] = make_pair(v[i]-w[i]*x,i+1);
  }
  sort(p,p + n);
  double co = 0;
  for(int i = 0;i < k;i++) co += p[n-i-1].first;
  return co >= 0;
}

int main(){
  scanf("%d%d",&n,&k);
  for(int i = 0;i < n;i++){
    scanf("%d%d",&v[i],&w[i]);
  }
  double lb = 0,ub = 1e8;
  for(int i = 0;i < 50;++i){
    double mid = (ub + lb) / 2;
    if(ans(mid)) lb = mid;
    else ub = mid;
  }
  
  ans(lb);
  
  for(int i = 0;i < k;i++){
    printf("%d ",p[n-i-1].second);
  }
  printf("\n");
  
  return 0;
}