题解 P1080 【国王游戏】
hicc0305
2018-07-05 14:56:39
这道题首先想到需要排序，可是按什么顺序排呢？
这就需要推导了
对于任意一个人i和j，假设i在j前面，i之前所有人的乘积为k1,i~j之间（不包括i，j）的乘积为k2
则此时两人的最大值为max(k1/bi,k1·ai·k2/bj)
如果交换两人的最大值为max(k2/bj,k1·aj·k2/bi)
显然k1·ai·k2/bj>k2/bj,k1·aj·k2/bi>k1/bi
所以如果k1·aj·k2/bi<k1·ai·k2/bj即aj·bj<ai·bi，交换后的最大值就比交换前的最大值小，就需要交换。按照这个比较法sort一下就可以了
剩下的就是枚举1~n，每一个都算一遍取最大。（注意要用高精，打的有点乱。。）
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
int ans[100000],la=0,res[100000];
struct peo
{
int a,b;
}p[1100];
bool cmp(peo x,peo y)
{
return (x.a*x.b)<(y.a*y.b);//按照 两个值的乘积进行排序
}
int m[100000],l=1;
void mutiply(int x)//高精乘法
{
int add=0;
for(int i=1;i<=l+10;i++)
{
int tmp=m[i]*x+add;
m[i]=tmp%10;
add=tmp/10;
}
l+=10;
while(m[l]==0) l--;
}
void get(int x)
{
memset(res,0,sizeof(res));
int tmp,l1=0;
for(int i=l;i>=1;i--)
{
tmp=tmp*10+m[i],l1++;
if(tmp<x) continue;
res[l1]=tmp/x;
tmp%=x;
}//高精除法，注意我存的时候正过来存的，所以还要倒过来一下
for(int i=1;i<=(l1+1)/2;i++)
swap(res[i],res[l1-i+1]);
while(res[l1]==0 && l1>1) l1--;
//比较大小
if(l1>la)
{
la=l1;
for(int i=la;i>=1;i--)
ans[i]=res[i];
}
else if(l1==la)
{
int f=0;
for(int i=la;i>=1;i--)
{
if(ans[i]<res[i])
{
f=1;
break;
}
if(ans[i]>res[i]) break;
}
if(f)
{
for(int i=la;i>=1;i--)
ans[i]=res[i];
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<=n;i++)
scanf("%d%d",&p[i].a,&p[i].b);
sort(p+1,p+n+1,cmp);
m[1]=1;
for(int i=1;i<=n;i++)
{
mutiply(p[i-1].a);
get(p[i].b);
}
if(ans[la]==0) la--;
for(int i=la;i>=1;i--)
printf("%d",ans[i]);
return 0;
}
```