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

思路

这道题其实主要的难点是如何排序。
排序之后贪心就非常简单了。

考虑
设 $s_i=\prod _{j=0}^i{a}_j$。

首先考虑交换前，第 $i$ 个上的值是 $\frac{s_{i-1}}{b_i}$，第 $i+1$个 是 $\frac{s_{i-1}\times a_i}{b_{i+1}}$
$an{s}_1=\max (\frac{s_{i-1}}{b_i},\frac{s_{i-1}\times a_i}{b_{i+1}})$

交换后 $i$ 的位置就变成了 $i+1$，$i+1$ 的位置就变成了 $i$。
值分别为 $\frac{s_{i-1}}{b_{i+1}}$，$\frac{s_{i-1}\times a_{i+1}}{b_i}$
$an{s}_2=\max (\frac{s_{i-1}}{b_{i+1}},\frac{s_{i-1}\times a_{i+1}}{b_i})$

显然 $\frac{s_{i-1}}{b_i}<\frac{s_{i-1}\times a_{i+1}}{b_i}$
并且 $\frac{s_{i-1}}{b_{i+1}}<\frac{s_{i-1}\times a_i}{b_{i+1}}$
如果 $an{s}_1<an{s}_2$
那么 $\frac{s_{i-1}\times a_i}{b_{i+1}}<\frac{s_{i-1}\times a_{i+1}}{b_i})$
通过化简，得：
$$a_i\cdot b_i<a_{i+1}\cdot b_{i+1}$$
由此可见，对 $a\ast b$ 进行关键字排序就可以了。
这题还需要高精度！！！

$Code$

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;long long ff[10100],f[10100],ans[10100];long long n,js=1;struct node{   	long long x,y;}a[1000010];bool cmp(const node&d,const node&dd){   	return d.x*d.y<dd.x*dd.y;}void gjc(int x){   	int jw=0;	for(int i=1; i<=10000; i++)	 {   	 	f[i]=f[i]*x+jw;	 	jw=f[i]/10;	 	f[i]%=10;	 }}void gju(int x){   	int j=10000,jw=0;	while(f[j]==0)	  j--;	for(int i=j; i>=1; i--)	 {   	 	ff[i]=(f[i]+jw*10);	 	jw=ff[i]%x;	 	ff[i]/=x;	 }}void gjbj(){   	int j=10000;	while(ans[j]==0)	   j--;	int jj=10000;	while(ff[jj]==0)	   jj--;	if(jj>j)	 for(int i=1; i<=jj; i++)	    ans[i]=ff[i];	else if(jj==j)	 for(int i=jj; i>=1; i--)      if(ans[i]<ff[i])       {          	 for(int i=1; i<=jj; i++)	        ans[i]=ff[i];	     break;	   }	  else if(ans[i]>ff[i])	     break;    memset(ff,0,sizeof(ff));}int main(){   	cin>>n;	for(int i=1; i<=n+1; i++)	   scanf("%lld%lld",&a[i].x,&a[i].y);	sort(a+2,a+2+n,cmp);	f[1]=1;	for(int i=2; i<=n+1; i++)	 {   	   gjc(a[i-1].x);	   gju(a[i].y);	   gjbj();	 }	int j=10000;	while(ans[j]==0)	   j--;	for(int i=j; i>=1; i--)	   cout<<ans[i];	return 0;}