描述
恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
格式
输入格式
第一行包含一个整数n，表示大臣的人数。
第二行包含两个整数a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。接下来n行，每行包含两个整数a和b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式
输出只有一行，包含一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
限制
每个测试点1s
提示
对于20%的数据，有1≤ n≤ 10，0 < a、b < 8；
对于40%的数据，有1≤ n≤20，0 < a、b < 8；
对于60%的数据，有1≤ n≤100；
对于60%的数据，保证答案不超过10^9；
对于100%的数据，有1 ≤ n ≤1,000，0 < a、b < 10000。
题解
题做着做着就觉得自己什么都弱，什么都不会……
首先最“暴力”的贪心，40分。
</pre><pre name="code" class="cpp">#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define mod 1000000007
using namespace std;
int n;
struct ren{ll a,b;} p[1002];
bool kp(const ren &i,const ren &j)
{
if(i.b<j.b) return true;
else if(i.b==j.b&&i.a<j.a) return true;
else return false;
}
void init()
{
scanf("%d",&n);
int i;
scanf("%lld%lld",&p[0].a,&p[0].b);
for(i=1;i<=n;i++)
scanf("%lld%lld",&p[i].a,&p[i].b);
sort(p+1,p+n+1,kp);
ll ji=p[0].a,ans=0;
for(i=1;i<=n;i++)
{ans=max(ans,ji/p[i].b);
ji*=p[i].a;
}
printf("%I64d\n",ans);
}
int main()
{
init();
return 0;
}
然后是贪心方面的正解，
设前i-1个人的顺序已确定，两个人分别为i和i+1。两人的可获的金币数为v[i]和v[i+1]。
记w[i]=a[1]*a[2]*a[3]*...*a[i]。则：v[i]=w[i-1]/b[i]；v[i+1]=w[i]/b[i+1]=v[i]*a[i]*b[i]/b[i+1]。因为前i-1个人的顺序已确定，所以可以选择按a[i]*b[i]从小到大排序。
开了long long60分。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n;
struct ren{int a,b;} r[1002];
bool kp(const ren &i,const ren &j)
{
return i.b*i.a<j.a*j.b;
}
void init()
{
scanf("%d",&n);
int i;
scanf("%d%d",&r[0].a,&r[0].b);
for(i=1;i<=n;i++)
scanf("%d%d",&r[i].a,&r[i].b);
sort(r+1,r+n+1,kp);
}
int main()
{
init();
ll ans=0,ji=r[0].a;
for(int i=1;i<=n;i++)
{ans=max(ans,ji/r[i].b);
ji=ji*r[i].a;
}
printf("%lld\n",ans);
return 0;
}
所以正解要加高精乘高精和高精除单精。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n,t[2502],ans[2502];
struct ren{int a,b;} r[1002];
int now[2502],next[2502];
bool kp(const ren &i,const ren &j) {return i.b*i.a<j.a*j.b;}
void init()
{
scanf("%d",&n);
int i;
scanf("%d%d",&r[0].a,&r[0].b);
for(i=1;i<=n;i++)
scanf("%d%d",&r[i].a,&r[i].b);
sort(r+1,r+n+1,kp);
}
void div(int c[],int x)
{
if(!x) return;
memset(t,0,sizeof(t));
int i,k=0;
for(i=c[0];i>=1;i--)
{
t[i]=(k*10000+c[i])/x;
k=(k*10000+c[i])%x;
}
t[0]=c[0];
while(!t[t[0]] && t[0]>0) t[0]--;
}
void mul(int x[],int y[])
{
memset(t,0,sizeof(t));
int i,j;
for(i=1;i<=x[0];i++)
for(j=1;j<=y[0];j++)
{
t[i+j-1]+=x[i]*y[j];
if(t[i+j-1]>9999)
{t[i+j]+=t[i+j-1]/10000; t[i+j-1]%=10000;}
}
i=x[0]+y[0]; t[0]=x[0]+y[0];
while(t[i]>9999)
{
t[i+1]+=t[i]/10000;
t[i]%=10000;
i++; t[0]++;
}
while(!t[t[0]] && t[0]>0) t[0]--;
}
bool check()
{
if(t[0]<ans[0]) return false;
else if(t[0]>ans[0]) return true;
else
{int i;
for(i=ans[0];i>0;i--)
{if(t[i]>ans[i]) return true;
if(t[i]<ans[i]) return false;
}
}
}
void work()
{
int i,j;
while(r[0].a>0)
{now[0]++;
now[now[0]]=r[0].a%10000; r[0].a/=10000;
}
for(i=1;i<=n;i++)
{div(now,r[i].b);
if(check())
{for(j=0;j<=t[0];j++) ans[j]=t[j];}
memset(next,0,sizeof(next));
while(r[i].a>0)
{next[0]++;
next[next[0]]=r[i].a%10000; r[i].a/=10000;
}
mul(now,next);
memset(now,0,sizeof(now));
for(j=0;j<=t[0];j++) now[j]=t[j];
}
}
void PRINT()
{
int i;
if(ans[0]<=1) {printf("%d\n",ans[1]); return ;}
else
{printf("%d",ans[ans[0]]);
for(i=ans[0]-1;i>=1;i--)
{if(ans[i]/1000==0) printf("0");
if(ans[i]/100==0) printf("0");
if(ans[i]/10==0) printf("0");
if(ans[i]/1==0) printf("0");
if(ans[i]) printf("%d",ans[i]);
}
}
printf("\n");
}
int main()
{
init(); work(); PRINT();
return 0;
}