C++(g++ 7.5.0) 解法, 执行用时: 660ms, 内存消耗: 4688K, 提交时间: 2023-04-09 11:16:39

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

typedef double fl;
const int N=100010;
int n,k,a[N],b[N];
fl v[N];

bool check(fl x) {
	for(int i=1; i<=n; ++i)
		v[i]=b[i]-x*a[i];
	sort(v+1,v+n+1);
	fl res=0;
	for(int i=n; i>n-k; --i)
		res+=v[i];
	return res>1e-8;
}

int main() {
	int T;
	cin>>T;
	while(T--) {
		cin>>n>>k;
		for(int i=1; i<=n; ++i)
			scanf("%d%d",&a[i],&b[i]);
		fl l=0,r=1000010;
		while(r-l>1e-4) {
			fl mid=(l+r)/2;
			if(check(mid))l=mid;
			else r=mid;
		}
		printf("%.2lf\n",l);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 690ms, 内存消耗: 2016K, 提交时间: 2018-04-05 10:59:34

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100005
int t,n,k,i,j,a[MAXN],b[MAXN];
double l,r,m,d[MAXN],x;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&k);
		for(i=0;i<n;i++)scanf("%d%d",a+i,b+i);
		l=r=0;
		for(i=0;i<n;i++)if(b[i]>r)r=b[i];
		while(l+1e-5<r)
		{
			m=(l+r)/2;
			for(i=j=0;i<n;i++)d[i]=b[i]-a[i]*m;
			sort(d,d+n,greater<double>());
			for(i=x=0;i<k;i++)x+=d[i];
			if(x>=0)l=m;
			else r=m;
		}
		printf("%.2lf\n",l);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 1657ms, 内存消耗: 4632K, 提交时间: 2020-10-07 19:02:55

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int v[N],w[N],n,k;
double f[N];
bool ck(double x){
	double sum=0;
	for(int i=0;i<n;i++) f[i]=1.0*w[i]*x-1.0*v[i];
	sort(f,f+n);
	for(int i=0;i<k;i++) sum+=f[i];
	return sum>=0;
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);
		double L=0,R=1e6,M;
		for(int i=0;i<100;i++){
			M=(L+R)/2.0;
			if(ck(M)) R=M;
			else L=M;
		}
		printf("%.2lf\n",L);
	}
}