[2016-2017 ACM-ICPC CHINA-Final][GYM 101194 E] Bet

    题意： 有n支队伍，若给第i支队伍下注\(x_i\)，第i支队伍赢的话就能获得\(x_i+\frac{B_i}{A_i}\)的收益。现在要你选出若干支队伍并下注，使得在选出的队伍中有且仅有一支队伍赢的情况下，无论是哪支队伍赢，都能赚到钱（收益大于总下注额）。求最多能选出多少支队伍。(\(n<=100,0<A_i,B_i<100\)，保证\(A_i,B_i\)小数点后只有三位)

    题解：假设选出了\(k\)支队伍，第i支队伍下注\(x_i\)，总共下注了\(sum\)，那么为了满足条件，必有\[x_i+x_i\cdot \frac{B_i}{A_i}>sum\]

    将式子变形为\(x_i>\frac{A_i}{A_i+B_i}sum\)，将\(i=1...n\)下的式子相加，可以得到\[sum>\sum{\frac{A_i}{A_i+B_i}}sum\]

    显然选出队伍满足条件的必要条件是\(\sum{\frac{A_i}{A_i+B_i}}<1\)。下面证明其充分性。

    设\(sum=1\)，则\(\sum{x_i}=1\)，取\(x_i=\frac{A_i}{A_i+B_i}\frac{1}{\sum{\frac{A_i}{A_i+B_i}}}>\frac{A_i}{A_i+B_i}sum\)且\(\sum{x_i}=1\)，所以条件为充分条件。

    显然只要按\(\frac{A_i}{A_i+B_i}\)排序，取出最多的就可以了。

    式子推导很简单，但是为什么过的人这么少呢？

    因为这题卡精度！

    做除法时要精确到小数点后50位（据说，我直接开了100位）以及读入的时候由于会出现读入1.0存储为0.999的情况，所以读入也要手动处理过。

    写了一个高精小数除，充分认识到了java的重要性以及自己的弱小。

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;

struct BigNum
{
	int a[250],len;

	void Init(double x=0,int tlen=99)
	{
		memset(a,0,sizeof(a));
		int t=(int)x;
		len=100;
		if (t==0) len=101;
		while (t) a[len++]=t%10,t/=10;
		x-=(int)x;
		if (tlen==3)
		{
			x*=1000;
			if (x-(int)x>0.8) t=(int)x+1;
			else t=(int)x;
			a[99]=t/100;
			a[98]=t/10%10;
			a[97]=t%10;
		}
		else
		for (int i=99;i>=99-tlen;i--)
		{
			x*=10;
			a[i]=(int)x;
			x-=(int)x;
		}
		while (len>1 && a[len-1]==0) len--;
	}

	BigNum() {Init();}
	void Print()
	{
		for (int i=max(len-1,100);i>=100;i--) printf("%d",a[i]);
		printf(".");
		for (int i=99;i>=95;i--) printf("%d",a[i]);
		printf("\n");
	}
	friend BigNum operator + (const BigNum &a,const BigNum &b);
	friend BigNum operator - (const BigNum &a,const BigNum &b);
	friend BigNum operator / (const BigNum &a,const BigNum &b);
	friend void Mul10(BigNum *a);
	friend void Div10(BigNum *a);
	friend bool operator < (const BigNum &a,const BigNum &b);
	friend bool operator <= (const BigNum &a,const BigNum &b);
}k[maxn],c0,c1;

bool operator < (const BigNum &a,const BigNum &b)
{
	if (a.len<b.len) return true;
	if (a.len>b.len) return false;
	for (int i=a.len-1;i>=0;i--)
		if (a.a[i]<b.a[i]) return true;
		else if (a.a[i]>b.a[i]) return false;
	return false;
}

bool operator <= (const BigNum &a,const BigNum &b)
{
	if (a.len<b.len) return true;
	if (a.len>b.len) return false;
	for (int i=a.len-1;i>=0;i--)
		if (a.a[i]<b.a[i]) return true;
		else if (a.a[i]>b.a[i]) return false;
	return true;
}

BigNum operator + (const BigNum &a,const BigNum &b)
{
	BigNum tmp;
	tmp.Init();
	int md=0;
	tmp.len=max(a.len,b.len);
	for (int i=0;i<tmp.len;i++)
	{
		tmp.a[i]=a.a[i]+b.a[i]+md;
		md=tmp.a[i]/10;
		tmp.a[i]%=10;
	}
	if (md) tmp.a[tmp.len++]=md;
	while (tmp.len>1 && tmp.a[tmp.len-1]==0) tmp.len--;
	return tmp;
}

BigNum operator - (const BigNum &a,const BigNum &b)
{
	BigNum tmp=a;
	int md=0;
	for (int i=0;i<tmp.len;i++)
	{
		tmp.a[i]-=b.a[i]+md;
		if (tmp.a[i]<0) md=1,tmp.a[i]+=10;
		else md=0;
	}
	while (tmp.len>1 && tmp.a[tmp.len-1]==0) tmp.len--;
	return tmp;
}

BigNum operator * (const BigNum &a,const int &b)
{
	BigNum tmp;
	tmp.Init();
	int md=0;
	for (int i=0;i<tmp.len;i++)
	{
		tmp.a[i]=tmp.a[i]*b+md;
		md=tmp.a[i]/10;
		tmp.a[i]%=10;
	}
	if (md) tmp.a[tmp.len++]=md;
	while (tmp.len>1 && tmp.a[tmp.len-1]==0) tmp.len--;
	return tmp;
}

void Mul10(BigNum *a)
{
	for (int i=a->len;i>=1;i--) a->a[i]=a->a[i-1];
	a->a[0]=0;
	a->len++;
}

void Div10(BigNum *a)
{
	for (int i=0;i<a->len-1;i++) a->a[i]=a->a[i+1];
	a->a[a->len-1]=0;
	a->len--;
}

BigNum operator / (const BigNum &a,const BigNum &b)
{
	BigNum tmp,a2=a,b2=b;
	tmp.Init();
	tmp.len=100;
	while (b2<=a2) Mul10(&b2),tmp.len++;
	for (int i=tmp.len;i>=0;i--)
	{
		while (b2<=a2 && !(b2<=c0))
			tmp.a[i]++,a2=a2-b2;
		Div10(&b2);
	}
	while (tmp.len>1 && tmp.a[tmp.len-1]==0) tmp.len--;
	return tmp;
}

double a[maxn],b[maxn];
int n;

int main()
{
	int T;
	c0.Init(0);
	c1.Init(1);
	scanf("%d",&T);
	for (int t=1;t<=T;t++)
	{
		printf("Case #%d: ",t);
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%lf:%lf",&a[i],&b[i]);
			BigNum x,y;
			x.Init(a[i],3);
			y.Init(a[i]+b[i],3);
			x=x/y;
			k[i]=x;
		}
		sort(k+1,k+1+n);
		BigNum sum;
		sum.Init(0);
		for (int i=1;i<=n+1;i++)
		{
			if (i==n+1)
			{
				printf("%d\n",n);
				break;
			}
			sum=sum+k[i];
			if (c1<=sum)
			{
				printf("%d\n",i-1);
				break;
			}
		}
	}
	return 0;
}

    后来发现这题竟然只卡读入精度......

#include <bits/stdc++.h>
using namespace std;
const int maxn=110;

double a[maxn],b[maxn];
long double k[maxn];
int n;

int main()
{
	int T;
	scanf("%d",&T);
	for (int t=1;t<=T;t++)
	{
		printf("Case #%d: ",t);
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		{
			scanf("%lf:%lf",&a[i],&b[i]);
			k[i]=1.0*floor(1000*a[i])/(floor(1000*a[i])+floor(1000*b[i]));
		}
		sort(k+1,k+1+n);
		long double sum=0;
		for (int i=1;i<=n+1;i++)
		{
			if (i==n+1)
			{
				printf("%d\n",n);
				break;
			}
			sum+=k[i];
			if (sum>=1.0)
			{
				printf("%d\n",i-1);
				break;
			}
		}
	}
	return 0;
}