POJ-2976, ZOJ-3068 : Dropping tests

問題概要

平均値の最大化。

acceptされたコード

計算量O(N*log N * 二分探索)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1000;

double X;

int N, K;
int ws[MAX_N], vs[MAX_N], ids[MAX_N];

bool init(){
	scanf("%d%d", &N, &K);
	for(int i=0; i<N; i++){
		scanf("%d", vs+i);
	}
	for(int i=0; i<N; i++){
		scanf("%d", ws+i);
		ids[i] = i;
	}

	return N > 0;
}

bool cmp(int i, int j){
	return vs[i] - X*ws[i] > vs[j] - X*ws[j];
}

bool check(double x){
	X = x;
	sort(ids, ids+N, cmp);

	double total = 0.0;
	for(int i=0; i<N-K; i++){
		total += vs[ids[i]] - X*ws[ids[i]];
	}

	return total <= 0.0;
}

int solve(){
	double low = 0.0, high = 1.0;
	for(int loop=0; loop<20; loop++){
		double mid = (high + low) / 2.0;
		if(check(mid)){
			high = mid;
		}
		else{
			low = mid;
		}
	}

	return (int)(100 * low + 0.5);
}

int main(){
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}