Python3 解法, 执行用时: 693ms, 内存消耗: 7588K, 提交时间: 2023-08-02 11:45:58

T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    dolls = [list(map(int, input().split())) for _ in range(n)]
    l, r = 0, max([v/c for c, v in dolls])
    while r - l > 1e-5:
        mid = (l + r) / 2
        dolls.sort(key=lambda x: x[1] - mid * x[0], reverse=True)
        sum = 0
        for i in range(k):
            sum += dolls[i][1] - mid * dolls[i][0]
        if sum >= 0:
            l = mid
        else:
            r = mid
    print(int(l))

C++11(clang++ 3.9) 解法, 执行用时: 73ms, 内存消耗: 852K, 提交时间: 2020-05-23 23:01:58

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

int T,n,k,a[10003],b[10003],c[10003];

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		cin>>b[i]>>a[i];
		int l=0,r=10000;
		while(l<r)
		{
			int mid=l+r+1>>1;
			long long sum=0;
			for(int i=1;i<=n;i++)
			c[i]=a[i]-mid*b[i];
			sort(c+1,c+n+1);
			for(int i=1;i<=k;i++)
			sum+=c[n+1-i];
			if(sum>=0)
			l=mid;
			else
			r=mid-1;
		}
		cout<<l<<endl;
	}
}