本文共 2072 字，大约阅读时间需要 6 分钟。

去年这题按右手排序骗了45好像。。

恩 其实这是一个贪心题

USACO 50题精选中有一个按加法排序的

这个题需要按乘法排序

如何考虑

假设前i个左手乘积X

相连两个

第一个

1.A B

第二个

2..C D

则按 1 2 的顺序排

X/B  X*A/D 

将两人互换后 

X/D  X*C/B

显然

 X*A/D>X/D

X*C/B>X/B

我们只需讨论X*A/D和X*C/B的关系 就可以确定这两种哪一种更好

我们发现 X*A/D和X*C/B==>A/D和C/B

A/D和C/B 同乘B*D 变成 A*B和C*D

A/D<C/B充要条件是A*B<C*D (A,B,C,D都为正整数)

所以按乘积从小到大排序 然后统计每一个大臣的获益 最大值输出即可

有的同学直接输出的最后一个大臣的 好像有一个点WA。。。

原因不明 个人感觉不一定在最后才取最值

用到了高精*单精  高精/单精

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int lim=1111;int m,z[lim];struct self{int x,y,z;}s[lim];int l[lim];int a,b,c,d;int cmp(self a1,self a2){    return a1.z
       
        =1;a--)    {        if(s[a]<1000)cout<<0;        if(s[a]<100)cout<<0;        if(s[a]<10)cout<<0;        cout<
        
         =10000) { s[a+1]=s[a+1]+s[a]/10000; s[a]%=10000; s[0]=max(s[0],a+1); }}void cheng(int s[lim],int x){ int a; for(a=1;a<=s[0];a++)s[a]*=x; jinwei(s);}void copy(int f[lim],int t[lim]){ int a; for(a=0;a<=f[0];a++)t[a]=f[a];}bool dayu(int f[lim],int t[lim]){ int a; if(f[0]>t[0])return true; if(f[0]
         
          =1;a--) { if(f[a]>t[a])return true; if(f[a]
          
           =1;a--) { t[a]=w[a]/x; if(t[a]!=0)t[0]=max(t[0],a); w[a]=w[a]-t[a]*x; w[a-1]=w[a]*10000+w[a-1]; w[a]=0; } if(dayu(t,z))copy(t,z);}int main(){ scanf("%d",&m); m++; for(a=1;a<=m;a++) { scanf("%d%d",&s[a].x,&s[a].y); s[a].z=s[a].x*s[a].y; } sort(s+2,s+m+1,cmp); l[1]=s[1].x;l[0]=1; for(a=2;a<=m;a++) { querymin(l,s[a].y); cheng(l,s[a].x); } print(z); return 0;}
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/14445427 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！