题源:国王游戏
分析:贪心思想:对于每个大臣有a,b表示左右手数,可证明a*b大的放后面可得最优解
有关证明:(本来想来张手写图的,传不上去 证明
具体算法:数据规模n达到10000,由于是连乘,可能会溢出采用高精度乘法,除法
重载运算符结构体排序
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
struct k
{
int a,b,ab;
}p[10005];
int temp1[100000],temp2[100000],ans[100000];
bool cmp(k p1,k p2)
{
return p1.ab<p2.ab;
}
void multi(int x)
{
for(int i=1;i<=temp1[0];i++)
{
temp1[i]*=x;
}
for(int i=1;i<=temp1[0];i++)
{
temp1[i+1]+=temp1[i]/10;
temp1[i]%=10;
if(i==temp1[0]&&temp1[i+1])temp1[0]++;
}
}
void divide(int x)
{
memset(temp2,0,sizeof(temp2));
int m=0;
for(int i=temp1[0];i>=1;i--)
{
m=m*10+temp1[i];
temp2[i]=m/x;
if(temp2[0]==0&&temp2[i])temp2[0]=i;
m%=x;
}
for(int i=1;i<=temp2[0];i++)
{
temp2[i+1]+=temp2[i]/10;
temp2[i]%=10;
if(i==temp2[0]&&temp2[i+1])temp2[0]++;
}
}
int cmpr()
{
if(temp2[0]<ans[0])return 0;
if(temp2[0]>ans[0])return 1;
for(int i=ans[0];i>=1;i--)
{
if(temp2[i]>ans[i])return 1;
else return 0;
}
return 0;
}
void cpy()
{
for(int i=0;i<=temp2[0];i++)
{
ans[i]=temp2[i];
}
}
int n;
int main()
{
ios::sync_with_stdio(false);
temp1[1]=temp1[0]=1;
cin>>n;
for(int i=0;i<=n;i++)
{
cin>>p[i].a>>p[i].b;
p[i].ab=p[i].a*p[i].b;
}
sort(p+1,p+1+n,cmp);
for(int i=1;i<=n;i++)
{
multi(p[i-1].a);
divide(p[i].b);
if(cmpr())cpy();
}
for(int i=ans[0];i>=1;i--)
{
cout<<ans[i];
}
return 0;
}