POJ - 2976 Dropping tests && 0/1 分数规划

POJ - 2976 Dropping tests

你有 \(n\) 次考试成绩， 定义考试平均成绩为 $$\frac{\sum_{i = 1}^{n} a_{i}}{\sum_{i = 1}^{n} b_{i}}$$

你可以考虑放弃 \(K\) 次成绩， 求最大平均成绩 * 100

---

小插曲： 被精度卡成喜羊羊

---

0/1分数规划\(from\)人生导师

Solution

01分数规划（不是很）裸题， 在每次 \(check\) 时， 选取较大的 \(num - K + 1\) 次即可

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

using namespace std;

double RD(){

    double out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 2019;

int num, K;

double a[maxn], b[maxn],c[maxn];

bool check(double k){

	for(int i = 1;i <= num;i++){

		c[i] = a[i] - b[i] * k;

		}

	sort(c + 1, c + 1 + num);

	double temp = 0;

	for(int i = num;i > K;i--)temp += c[i];

	if(temp > 0)return 1;

	return 0;

	}

double search(double l, double r){

	double ans;

	while(r - l > 0.000000001){

		double mid = (l + r) / 2;

		if(check(mid))ans = mid, l = mid;

		else r = mid;

		}

	return ans;

	}

int main(){

	while(1){

		num = RD(), K = RD();

		if(!num && !K)return 0;

		for(int i = 1;i <= num;i++)a[i] = RD();

		for(int i = 1;i <= num;i++)b[i] = RD();

		printf("%.0f\n",100 * search(0, 1000000019));

		}

	}