题解 | #gpa#

【A.gpa题解】

直接二分答案（答案为小数，注意精度）。

对于当前答案D，如果有更大的结果，则$\sum \left(s\right[i\left]c\right[i\left]\right)/\sum s\left[i\right]>D\backslash sum\; (s[i]c[i])/\backslash sum\; s[i]\; >\; D$∑(s[i]c[i])/∑s[i]>D，即$\sum \left(s\right[i\left]c\right[i\left]\right)>\sum \left(s\right[i\left]D\right)\Rightarrow \sum \left(s\right[i\left]\right(c\left[i\right]-D)>0\backslash sum\; (s[i]c[i])>\; \backslash sum\; (s[i]D)\; \backslash Rightarrow\; \backslash sum\; (s[i](c[i]-\; D)\; >\; 0$∑(s[i]c[i])>∑(s[i]D)⇒∑(s[i](c[i]−D)>0，删掉最小的k个，判断正负。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
const double eps = 1e-5;

int n, k;
double s[N], c[N], val[N];

bool check(double D) {
	double sum = 0;
	for(int i = 1; i <= n; i++)	val[i] = s[i] * (c[i] - D);
	sort(val+1, val+1+n, [](double x, double y) {
		return x > y;
	});
	for(int i = 1; i <= n - k; i++)	sum += val[i];
	if(sum >= 0)	return true;
	else	return false;
}

signed main() {
	cin>>n>>k;
	for(int i = 1; i <= n; i++)	cin>>s[i];
	for(int i = 1; i <= n; i++)	cin>>c[i];
	double l = 0, r = 1000.0;
	while(r - l > eps) {
		double mid = (l + r) / 2.0;
		if(check(mid))	l = mid;
		else	r = mid;
	}
	cout<<setprecision(12)<<fixed<<l;
	return 0;
}