这一次高精度完美地过辣好开心OvO,还get到了非常方便的高精度除小于10000的方法,这个是我自己脑出来的OvO
看来下午高精度傻逼得值qvq
原题:
恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右 手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排 成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每 位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右 手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序, 使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。
1 ≤ n ≤1,000,0 < a、b < 10000。
最大的最小,看上去好像二分的样子,然而没有单调性没法二分
可以先只看两个之间,只看这两个人的话前面的都不用管了,如果a1/b2>a2/b1,=>a1*b1>a2*b1,然后交换这两个就可以让这两个人中较大的更小
(网上题解是这么说的,我没看懂
然后按照a*b升序排序,模拟一下即可
数很大,要高精度
小技巧:
高精度除一个小于10000的数,直接用万进制从高位开始除,把除剩下的数也就是这一位膜除的数的结果乘10000加到下一位上去,继续往下除
结果的长度是被除数的长度-(被除数最高位>除数)
其它单精度数也可以这么玩儿,效率未知,应该不会太慢
好开心OvO
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int ss=;
int read(){int z=,mark=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mark=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mark;
}
int n; struct cdd{int a,b;}a[];
bool compare(cdd x,cdd y){ return x.a*x.b<y.a*y.b;}
int mul_a[],mul_b[],ans[];
int c[];
void copy(int *x,int *y){memset(y,,sizeof(y)); y[]=x[]; for(int i=;i<=x[];i++) y[i]=x[i];}
void cheng(int *x,int z){
for(int i=;i<=x[];i++) x[i]*=z;
for(int i=;i<=x[];i++) x[i+]+=x[i]/ss,x[i]%=ss;
while(x[x[]+]){ x[]++; x[x[]+]+=x[x[]]/ss,x[x[]]%=ss;}
}
bool bi(int *x,int *y){
if(x[]>y[]) return true;
if(x[]<y[]) return false;
for(int i=x[];i>=;i--)if(x[i]!=y[i]) return x[i]>y[i];
return true;
}
void chu(int *x,int *y,int z){//因为除的数<10000,刚好在万进制范围内,就直接除单精了
copy(y,c);
x[]=c[]-(c[c[]]<z);
for(int i=c[];i>=;i--){
x[i]=c[i]/z;
c[i-]+=(c[i]%z)*ss;
}
for(int i=;i<=x[];i++) x[i+]+=x[i]/ss,x[i]%=ss;
while(x[x[]+]){ x[]++; x[x[]+]+=x[x[]]/ss,x[x[]]%=ss;}
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n;
for(int i=;i<=n;i++) a[i].a=read(),a[i].b=read();
sort(a+,a+n+,compare);
mul_a[mul_a[]=]=a[].a;
for(int i=;i<=n;i++){
chu(mul_b,mul_a,a[i].b);
if(bi(mul_b,ans)) copy(mul_b,ans);
cheng(mul_a,a[i].a);
}
cout<<ans[ans[]];
for(int i=ans[]-;i>=;i--) printf("%04d",ans[i]);
cout<<endl;
return ;
}