贪心技巧

贪心

贪心其实就是按照某种规则排序。

乱搞

如果不知道应该按照什么规则排序，可以将自己能想到的所有排序方式都排一遍，从其中取更优秀的答案，排序次数越多只能使答案更优秀，所以放心排。

拟阵

先找对于只有两个数据的情况进行手玩。找到其中的排序方式，然后对于后面的任意两个数排序时（不一定是连续的），排序方式与只有两组数据时是相同的。

例题

luogu1080
先考虑只有两个大臣，只有两种情况（假如用l，r表示国王的左右手，l1,r1表示一号大臣，l2,r2表示二号大臣）：
如果1号大臣在前面，那么一号大臣得到的金币就是(frac{l}{r1}),二号大臣得到的金币就是(frac{l*l1}{r2})最终答案就是其中的max
如果2号大臣在前面那么一号大臣的得到的金币就是(frac{l}{r2})二号大臣得到的金币就是(frac{l*l2}{r1}),最终答案就是在其中取max
那么排序的时候就可以对于任意两个大臣按照这个进行比较，也就是假装其他大臣都不存在

bool cmp(node x,node y)
{
    int l=a[1].l;
    int k1=max(l/x.r,l*x.l/y.r);
    int k2=max(l/y.r,l*y.l/x.r);
    if(k1<=k2) return 1;
    return 0;
}

然后可以化简（仅仅为了好看）
在上面的基础上，我们可以看成比较谁哪种情况更大就让他更靠后，首先明显(frac{l}{r1})与(frac{l}{r2})的存在是没有意义的，因为有明显另外两种比他们更大。
然后还剩下(frac{l*l1}{r2})与(frac{l*l2}{r1})将l约去，然后将r1与r2分别乘过去，然后就成了比较l1r1与比较l2r2比较小的就是比较优秀的那个。
然后发现如果乱搞，按照l*r排序也是不难想到的。
因为这个题需要知道最终答案，所以要写个高精。

代码

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
struct bignum
{
	int a[100000],n;
	bignum ()
	{
		n=0;
		memset(a,0,sizeof(a));
	}
	bignum (int x)
	{
		n=0;
		memset(a,0,sizeof(a));
		while(x)
		{
			a[++n]=x%10;
			x/=10;
		}
	}
	void print()
	{
		for(int i=n;i>=1;--i)
			printf("%d",a[i]);
		printf("
");
	}
};
bignum operator * (const bignum &x,int y)
{
	bignum c=x;
	for(int i=1;i<=c.n;++i)
		c.a[i]*=y;
	for(int i=1;i<=c.n;++i)
	{
		if(c.a[i]>=10)
		{
			c.a[i+1]+=c.a[i]/10;
			c.a[i]%=10;
		}
		if(i==c.n&&c.a[i+1]!=0) c.n++;
	}	
	return c;
}
bignum operator / (const bignum &x,int y)
{
	bignum c;
	c.n=x.n;
	int n=c.n;
	int k=0,tmp=0;
	for(int i=n;i>=1;--i)
	{
		tmp=k*10+x.a[i];
		c.a[n--]=tmp/y;
		k=tmp%y;
	}
	while(c.a[c.n]==0&&c.n>0) c.n--;
	if(c.n==0) c.n++;
	return c;
}
bool operator < (const bignum &x,const bignum &y)
{
	if(x.n!=y.n) return x.n<y.n;
	for(int i=x.n;i>=1;--i)
		if(x.a[i]!=y.a[i]) return x.a[i]<y.a[i];
}
const int N=11000;
struct node
{
	int l;
	int r;
}e[N];
bool cmp(node x,node y)
{
	return x.l*x.r<y.l*y.r;
}/*
bool cmp(node x,node y)
{
    int l=e[1].l,r=e[1].r;
    int k1=max(l/x.r,l*x.l/y.r);
    int k2=max(l/y.r,l*y.l/x.r);
    if(k1<=k2) return 1;
    return 0;
}*/
int main()
{
	//freopen("2.in","r",stdin);
	int n;
	scanf("%d",&n);
	++n;
	for(int i=1;i<=n;++i)
		scanf("%d%d",&e[i].l,&e[i].r);
	sort(e+2,e+n+1,cmp);
	bignum ans(e[1].l),anss(0);
	int ans2=e[1].l,anss2=0;
	for(int i=2;i<=n;++i)
	{

		anss=max(anss,ans/e[i].r);
		anss2=max(anss2,ans2/e[i].r);
		ans=ans*e[i].l;
		ans2=ans2*e[i].l;

	}
	//printf("%d",anss);
	anss.print();
	return 0;
}