本文共 1014 字，大约阅读时间需要 3 分钟。

$n$个人,每个人有属性$A_i,B_i$

选出一些人给第$i$个人投钱$x_i$,使得$x_i\ast (1+\frac{B_i}{A_i})>\sum x_j$

问你最多能选出多少人投钱(投多少无所谓,不关心)

设最后选了$k$个人

化简一下$x_i\ast \frac{A_i+B_i}{A_i}>\sum _{j=1}^k{x}_j$

也就是$\frac{x_i}{\sum _{j=1}^k{x}_j}>\frac{A_i}{A_i+B_i}$

把$i$取值为$[1,k]$得到$k$个不等式,相加得到

$1>\sum \frac{A_i}{A_i+B_i}$

所以我们贪心选$\frac{A_i}{A_i+B_i}$小的,不大于一就行

#include 
   
    using namespace std;const int maxn = 1009;int casenum;long double p[maxn];int main(){
   	int t; cin >> t;	while( t-- )	{
   		int n; scanf("%d",&n);		long double x,y;		for(int i=1;i<=n;i++)		{
   			scanf("%Lf:%Lf",&x,&y);			p[i] = x/(x+y);		}		long double sum = 0;		sort( p+1,p+1+n );		int ans = 0;		for(int i=1;i<=n;i++)		{
   			sum += p[i];			if( sum>=1 )	break;			ans++;		}		printf("Case #%d: %d\n",++casenum,ans);	}}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/116046007 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！