本题大致题意是让金币拿的最多的人拿的最少，乍一看是一个贪心，如果直接想贪心策略，还是比较困难，此时我们可以利用贪心中的理论推导，来实现推出贪心策略
我们不妨设和为第一个大臣左手上的数和右手上的数
设和为第二个大臣左手上的数和右手上的数
设前面的其他大臣的左手上的数的乘积为
并且假设第一个大臣排在前面比第二个大臣排在前面要好一些
这是第一种排法(第一个大臣在前面)
此时的答案为
接下来考虑第二种排法(第一个大臣在前面)
此时的答案为
因为我们假设第一种比第二种排法优，则
根据不等式的性质，可以消掉
则
接下来再来运用不等式的性质，两边同时乘上
则原不等式等于
因为这些数都是正整数
所以
由于左边的最大值小于右边的最大值
所以
现在贪心推导出来了，只需要在排序的时候写上就可以了
接下来再来进行一些处理即可，注意用上高精度
下面来推广一下我的高精度模板
乘法
//高精度乘法
string cheng(string a1,string b1){
int lena=a1.size(),lenb=b1.size(),a[5005],b[5005],c[11005]={},lenc;
string c1;
for(int i=0;i<lena;i++) a[lena-i]=a1[i]-'0';
for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0';
for(int i=1;i<=lena;i++)
for(int j=1;j<=lenb;j++) c[i+j-1]+=a[i]*b[j],c[i+j]+=c[i+j-1]/10,c[i+j-1]%=10;
lenc=lena+lenb;
while(lenc>1 && c[lenc]==0) lenc--;
for(int i=lenc;i>=1;i--) c1+=c[i]+'0';
return c1;
}
除法
//高精度除法(除数为低精)
string chu(string a1,int b){
int lena=a1.size(),a[5005]={},c[5005]={},lenc=1;
string c1;
for(int i=0;i<lena;i++) a[i+1]=a1[i]-'0';
for(int i=1;i<=lena;i++) c[i]=a[i]/b,a[i+1]+=(a[i]-c[i]*b)*10,a[i]=0;
while(c[lenc]==0 && lenc<lena) lenc++;
for(int i=lenc;i<=lena;i++) c1+=c[i]+'0';
return c1;
}
上代码
#include<bits/stdc++.h>
using namespace std;
int n;
string jb,sum;
struct xs{
int x,y;
}a[1005];
bool cmp(xs a,xs b){
return a.x*a.y<b.x*b.y;
}
string cheng(string a1,string b1){
int lena=a1.size(),lenb=b1.size(),a[5005],b[5005],c[11005]={},lenc;
string c1;
for(int i=0;i<lena;i++) a[lena-i]=a1[i]-'0';
for(int i=0;i<lenb;i++) b[lenb-i]=b1[i]-'0';
for(int i=1;i<=lena;i++)
for(int j=1;j<=lenb;j++) c[i+j-1]+=a[i]*b[j],c[i+j]+=c[i+j-1]/10,c[i+j-1]%=10;
lenc=lena+lenb;
while(lenc>1 && c[lenc]==0) lenc--;
for(int i=lenc;i>=1;i--) c1+=c[i]+'0';
return c1;
}
string chu(string a1,int b){
int lena=a1.size(),a[5005]={},c[5005]={},lenc=1;
string c1;
for(int i=0;i<lena;i++) a[i+1]=a1[i]-'0';
for(int i=1;i<=lena;i++) c[i]=a[i]/b,a[i+1]+=(a[i]-c[i]*b)*10,a[i]=0;
while(c[lenc]==0 && lenc<lena) lenc++;
for(int i=lenc;i<=lena;i++) c1+=c[i]+'0';
return c1;
}
string z(int s){
int len;
string c1,c2;
while(s!=0){
c1+=s%10+'0';
s/=10;
}
len=c1.size();
for(int i=len-1;i>=0;i--)
c2+=c1[i];
return c2;
}
string ma(string a,string b){
int lena=a.size(),lenb=b.size();
if(lena>lenb) return a;
if(lena<lenb) return b;
if(a>b) return a;
return b;
}
int main(){
scanf("%d",&n);
int l,r;
cin>>l>>r;
for(int i=1;i<=n;i++)
scanf("%d %d",&a[i].x,&a[i].y);
sort(a+1,a+1+n,cmp);
sum=z(l);
for(int i=1;i<=n;i++){
string h=chu(sum,a[i].y);
sum=cheng(sum,z(a[i].x));
jb=ma(jb,h);
}
cout<<jb;
return 0;
}
共 2 条回复
棒~
%%% rp++ !