贪心题，我们使用邻项交换的方法求解。
我们假设当前有两个相邻的人分别为1,2，他们的左右手的数字分别为a,b，假设1之前的人的左手的数字之积为x，那么当前的答案为
我们将这两个人的位置交换，显然，这两个人位置的交换不会影响其他的人的答案，那么交换后的答案为
我们假设以上四个数分别为k1,k2,k3,k4，那么显然存在k4>k1,k2>k3
如果我们让交换前的答案更优，那么只需令k2<k4即可，整理，得
我们按照这个式子进行排序即可，另外，本题数据较大，我们需要高精度计算。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 struct peo { 8 ll l,r; 9 bool operator <(const peo &x) const { 10 return l*r<x.l*x.r; 11 } 12 }a[1010]; 13 int n; 14 ll ans[100010]={0,1},sum[100010]={0,1},maxx[100010]={0,1}; 15 int la=1,ls=1,lm=1; 16 void cheng(ll x) { 17 int tmp=0; 18 for(int i=1;i<=ls;i++) 19 sum[i]*=x; 20 for(int i=1;i<=ls;i++) { 21 tmp+=sum[i]; 22 sum[i]=tmp %10; 23 tmp/=10; 24 } 25 while(tmp) { 26 ls++; 27 sum[ls]=tmp%10; 28 tmp/=10; 29 } 30 } 31 void chu(ll x) { 32 memset(maxx,0,sizeof(maxx)); 33 lm=ls; 34 int tmp=0; 35 for(int i=lm;i>=1;i--) { 36 tmp*=10; 37 tmp+=sum[i]; 38 if(tmp>=x) { 39 maxx[i]=tmp/x; 40 tmp%=x; 41 42 } 43 } 44 while(maxx[lm]==0) { 45 if(lm==1) return ; 46 lm--; 47 } 48 } 49 void updata() { 50 if(lm>la) { 51 for(int i=1;i<=lm;i++) 52 ans[i]=maxx[i]; 53 la=lm; 54 return ; 55 } 56 for(int i=lm;i>=1;i--) 57 if(ans[i]<maxx[i]) { 58 for(int j=1;j<=la;j++) 59 ans[j]=maxx[j]; 60 return ; 61 } 62 } 63 int main() { 64 scanf("%d",&n); 65 scanf("%lld%lld",&a[0].l,&a[0].r); 66 for(int i=1;i<=n;i++) 67 scanf("%lld%lld",&a[i].l,&a[i].r); 68 sort(a+1,a+n+1); 69 for(int i=1;i<=n;i++) { 70 cheng(a[i-1].l); 71 chu(a[i].r); 72 updata(); 73 } 74 for(int i=la;i>=1;i--) 75 printf("%lld",ans[i]); 76 return 0; 77 }
原文：https://www.cnblogs.com/shl-blog/p/11042232.html
