Description:

At the university where she attended, the final score of her is img

Now she can delete at most k courses and she want to know what the highest final score that can get.

Input:

The first line has two positive integers n,k

The second line has n positive integers s[i]

The third line has n positive integers c[i]

Output:

Output the highest final score, your answer is correct if and only if the absolute error with the standard answer is no more than 1 0 5 10^{-5} 105

Sample Input:

3 1
1 2 3
3 2 1

Sample Output:

2.33333333333

Hint:

Delete the third course and the final score is 2 × 2 + 3 × 1 2 + 1 = 7 3 \frac{2\times2+3\times1}{2+1}=\frac{7}{3} 2+12×2+3×1=37

题目链接

n n n门课,每门课有两个属性 s s s c c c,删除 k k k门课,使 s [ i ] × c [ i ] s [ i ] \frac{\sum s[i]\times c[i]}{\sum s[i]} s[i]s[i]×c[i]最大。

01分数规划,设最终结果 m a x ( s [ i ] × c [ i ] s [ i ] ) = x max(\frac{\sum s[i]\times c[i]}{\sum s[i]})=x max(s[i]s[i]×c[i])=x,则 s [ i ] × c [ i ] x × s [ i ] = 0 \sum s[i]\times c[i]-x\times\sum s[i]=0 s[i]×c[i]x×s[i]=0,所以选择 ( s × c x × s ) (s\times c-x\times s) (s×cx×s)最大的 n k n-k nk门课,不断二分 x x x直到找到最大值并达到合适的精度。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout << #x << "=" << x << endl;
#define ArrayDebug(x,i) cout << #x << "[" << i << "]=" << x[i] << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e7 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
	char c;
	int sgn;
	if (c = getchar(), c == EOF) {
		return 0;
	}
	while (c != '-' && (c < '0' || c > '9')) {
		c = getchar();
	}
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while (c = getchar(), c >= '0' && c <= '9') {
		ret = ret * 10 + (c - '0');
	}
	ret *= sgn;
	return 1;
}
template <class T>
inline void out(T x) {
	if (x > 9) {
		out(x / 10);
	}
	putchar(x % 10 + '0');
}

int n, k;
vector<int> s, c;

bool check(double x) {
	vector<double> temp(n, 0.0);
	for (int i = 0; i < n; ++i) {
		temp[i] = 1.0 * s[i] * c[i] - x * s[i];
	}
	sort(temp.begin(), temp.end(), [&] (const double &a, const double &b) {
		return a > b;
	});
	double ans = 0;
	for (int i = 0; i < n - k; ++i) {
		ans += temp[i];
	}
	return ans > 0;
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	read(n); read(k);
	s.assign(n, 0);
	c.assign(n, 0);
	for (int i = 0; i < n; ++i) {
		read(s[i]);
	}
	for (int i = 0; i < n; ++i) {
		read(c[i]);
	}
	double left = 0, right = 1e3;
	while (right - left > eps) {
		double mid = (left + right) / 2;
		if (check(mid)) {
			left = mid;
		}
		else {
			right = mid;
		}
	}
	printf("%.8lf\n", left);
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}