POJ 3045 Cow Acrobats (贪心)-白红宇

POJ 3045 Cow Acrobats (贪心)

阅读量：4934 次

发布时间：2019-06-11

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

　　这是个贪心的题目,和网上的很多题解略有不同,我的贪心是从最下层开始,每次找到能使该层的牛的风险最小的方案,

　　记录风险值,上移一层,继续贪心.

　　最后从遍历每一层的风险值,找到其中的最大值

　　　我一开始对sum-p[i].a-p[i].b从小到大排序,这样第一次取出的就是能使最下层的牛的风险最小的方案,在上移一层时,这一层的风险值

　　为sum-p[i].a-p[i].b-p[0].a,由于p[0].a是固定值,所以第二次直接取出的就是能使该层的牛的风险最小的方案,依次类推..

　　　网上好多题解都是直接对p[i].a+p[i].b从大到小排序,其实本质上和我这个贪心是一样的,不过思考贪心的方式略有不同.

　　　此题有个坑点:可能一开始所有的风险值都为负的,我的minx初始化0就wa了好几次.minx要初始化为负无穷

/** Created:     2016年04月01日 09时11分08秒 星期五* Author:      Akrusher**/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         using namespace std;#define rep(i,a,n) for (int i=a;i
                         
                          =a;i--)#define in(n) scanf("%d",&(n))#define in2(x1,x2) scanf("%d%d",&(x1),&(x2))#define inll(n) scanf("%I64d",&(n))#define inll2(x1,x2) scanf("%I64d%I64d",&(x1),&(x2))#define inlld(n) scanf("%lld",&(n))#define inlld2(x1,x2) scanf("%lld%lld",&(x1),&(x2))#define inf(n) scanf("%f",&(n))#define inf2(x1,x2) scanf("%f%f",&(x1),&(x2))#define inlf(n) scanf("%lf",&(n))#define inlf2(x1,x2) scanf("%lf%lf",&(x1),&(x2))#define inc(str) scanf("%c",&(str))#define ins(str) scanf("%s",(str))#define out(x) printf("%d\n",(x))#define out2(x1,x2) printf("%d %d\n",(x1),(x2))#define outf(x) printf("%f\n",(x))#define outlf(x) printf("%lf\n",(x))#define outlf2(x1,x2) printf("%lf %lf\n",(x1),(x2));#define outll(x) printf("%I64d\n",(x))#define outlld(x) printf("%lld\n",(x))#define outc(str) printf("%c\n",(str))#define pb push_back#define mp make_pair#define fi first#define se second#define SZ(x) ((int)(x).size())#define mem(X,Y) memset(X,Y,sizeof(X));typedef vector
                          
                            vec;typedef long long ll;typedef pair
                           
                             P;const int dx[4]={ 1,0,-1,0},dy[4]={ 0,1,0,-1};const int INF=0x3f3f3f3f;const ll mod=1e9+7;ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}const bool AC=true;struct point{ int a,b,c;//a为weight,b为strength};bool cmp(point x,point y){ return x.c

转载于:https://www.cnblogs.com/akrusher/p/5344591.html

你可能感兴趣的文章