美文网首页算法笔记学习笔记
《算法笔记》4.4小节——算法初步->贪心

《算法笔记》4.4小节——算法初步->贪心

作者: 木子李_0961 | 来源:发表于2020-04-08 10:16 被阅读0次

    @[TOC]

    Contest100000584 - 《算法笔记》4.4小节——算法初步->贪心

    4.4小节——算法初步->贪心

    讲解和例题

    4.4.1 简单贪心

    在这里插入图片描述

    例题 PAT B1020 月饼

    1020 月饼

    来自 https://pintia.cn/problem-sets/994805260223102976/problems/type/7

    在这里插入图片描述
    在这里插入图片描述
    //PAT B1020 月饼 
    //2143 Problem  F   迷瘴
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    bool cmp(int a,int b)//按照从小到大排列 
    {
        return a<b;
    }
    
    int main()
    {
        int C;
        while(cin>>C)
        {
            while(C--)
            {//n种浓度的万能药水,体积V都相同,浓度不大于 W%
                int n,V,W;
                cin>>n>>V>>W;
                int P[n]={0};
                  
                for(int i=0;i<n;i++)//表示n种药水的浓度Pi%
                {
                    cin>>P[i];
                }
                sort(P,P+n,cmp);
                int res_V=V; double res_P=P[0];
                if(P[0]>W)//最低浓度不满足,则无法配置合格药水 
                {
                    res_V=0;res_P=0.00;
                }
                else
                {
                    for(int i=1;i<n;i++)
                    {
                        if((res_P*res_V+P[i]*V)/(res_V+V) <= W)//若预加入下一瓶药仍按满足,则混合下一瓶药 
                        {
                            res_P = (res_P*res_V+P[i]*V)/(res_V+V);
                            res_V += V;
                        }
                        else break;
                    }
                }
                printf("%d %.2f\n",res_V,res_P/100);
            }
            
            
        } 
        return 0;
    }
     
    

    例题2 PAT B1023组个最小数

    1023 组个最小数

    来自 https://pintia.cn/problem-sets/994805260223102976/problems/type/7

    在这里插入图片描述
    //PAT B1023 组个最小数 
    //PAT B1023 组个最小数 
    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    int main()
    {
        int cnt[10];//记录数字0~9的个数
        for(int i=0;i<10;i++)
        {
            scanf("%d",&cnt[i]);
        } 
        for(int i=1;i<10;i++)//从1~9中选择cnt不为0的最小的数字
        {
            if(cnt[i]>0)
            {
                printf("%d",i);
                cnt[i]--;
                break;//找到一个之后就中断   
            }
        } 
        for(int i=0;i<10;i++)//从0~9输出对应个数的数字 
        {
            for(int j=0;j<cnt[i];j++)
            {
                printf("%d",i);
            }
        } 
        
        return 0;
    } 
    

    4.4.2 区间贪心

    区间不相交问题:给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些区间两两没有交集。


    在这里插入图片描述
    //4.4.2区间贪心区间不相交问题
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int maxn = 110;
    struct Inteval
    {
        int x,y;//开区间左右端点 
    }I[maxn];
     
    bool cmp(Inteval a,Inteval b)
    {
        if(a.x != b.x) return a.x>b.x;//先按左端点从大到小排序
        else return a.y<b.y;//左端点相同的按右端点从小到大排序 
    }
     
    int main()
    {
        int n;
        while(scanf("%d",&n),n!=0)//什么骚操作??
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d%d",&I[i].x,&I[i].y);                        
            }        
            sort(I,I+n,cmp);//把区间排序
            //ans记录不相交区间个数,lastX记录上一个被选中区间的左端点
            int ans=1,lastX=I[0].x;
            for(int i=1;i<n;i++)
            {
                if(I[i].y <= lastX)//如果该区间右端点在lastX左边
                {
                    lastX = I[i].x;//以I[i]作为新选中的区间
                    ans++;//记录不想交区间个数        
                }        
            } 
            printf("%d\n",ans);
        } 
        return 0;
    }
     
    

    Codeup习题

    1126-ProblemA-看电视

    来自 http://codeup.cn/contest.php?cid=100000584
    题析:参考不相交区间问题,几乎一样

    //1126ProblemA看电视
    //参考不相交区间问题,几乎一样 
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    struct program//节目结构体 
    {
        int s;//节目开始时间
        int e;//节目结束时间 
    }pro[105];
    
    bool cmp(program a,program b)//比较规则 
    {
        if(a.s!=b.s) return a.s>b.s;//先按照节目开始时间从大到小排序
        else return a.e<b.e;//开始时间相同的按照结束时间从小到大排序   
    } 
    
    int main()
    {
        int n;
        while(scanf("%d",&n) != EOF && n!=0)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%d%d",&pro[i].s,&pro[i].e);//输入各个节目开始结束信息    
            }   
            sort(pro,pro+n,cmp);//节目排序
            //ans记录不冲突节目个数,lastX记录上一个被选中节目区间的开始时间 
            int ans=1,lastS=pro[0].s;//从一个时间段开始计数,所以初始值为1 
            for(int i=0;i<n;i++)
            {
                if(pro[i].e <= lastS)//如果该节目结束时间在lastS左边
                {//更新上一个时间段的开始时间 
                    lastS = pro[i].s;//以pro[i]作为新选中的节目段 
                    ans++;//记录不冲突节目个数 
                }   
            }   
            printf("%d\n",ans);  
        } 
        return 0;
    }
    

    1128-ProblemB-出租车费

    来自 http://codeup.cn/contest.php?cid=100000584
    题析:
    要找到分段与不分段的交界点在
    大佬讲解的很详细:
    https://blog.csdn.net/qian2213762498/article/details/81807247
    自己总结:

    在这里插入图片描述
    //1128ProblemB出租车费
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int n;
        while(scanf("%d",&n) != EOF)
        {
            if(n==0)
                break; 
            double money=0;
            if(n<=4)//第一段 
            {
                money = 10;
            }
            
            else if(n>4 && n<=8)//第二段 
            {
                money = 10+(n-4)*2;
            }
            else//第三段需要考虑是否分段 
            {
                while(n>=8)//先变量代换,这里还用n
                //特别注意此处的循环 
                {
                    money+=18;
                    n-=8;
                }
                if(n<=4)//不分段,继续分段函数三 
                {
                    money+=2.4*n;
                }
                else//分段,到分段函数二 
                {
                    money+=10+(n-4)*2;  
                }
            }
        //  cout<<money<<endl;
            int temp = (int)money;//最终花费整数部分
            if((money-temp)==0) 
            //  printf("%d\n",money);//之前money没转换为int型,一直报错 
                printf("%d\n",(int)money);
            else
                printf("%.1f\n",money);
        }
        return 0;
    }
     
    

    2031-ProblemC-To Fill or Not to Fill

    来自 http://codeup.cn/contest.php?cid=100000584
    题析:

    //2031 Problem  C   To Fill or Not to Fill
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    struct station
    {
        double price;
        double distance;
    }st[1010];
    
    bool cmp(struct station a,struct station b)
    {
        return a.distance < b.distance;
    }
    
    int main()
    {
        double Cmax,dis,Davg;
        int N;
        scanf("%lf%lf%lf%d",&Cmax,&dis,&Davg,&N);
        double maxdis = Cmax * Davg;//油箱满油最多能走的距离
        for(int i=0;i<N;i++)
        {
            scanf("%lf%lf",&st[i].price,&st[i].distance);   
        } 
        sort(st,st+N,cmp);//按照到起点(杭州)距离来排序加油站 
        st[N].distance = dis;//终点到杭州的距离为d
        st[N].price = 0;//终点不需要加油
        if(st[0].distance != 0)//起点没有油则无法开启行程 
        {
            printf("The maximum travel distance = 0.00\n");
        } 
        else
        {
            int cur_station = 0;//当前加油站编号
            double sumprice = 0,cur_oil = 0;
            while(cur_station < N)
            {
                int k = -1;//初始化油价最低的站号 
                double priceMin = 999999999;
                for(int i = cur_station+1;i<=N && (st[i].distance - st[cur_station].distance) <= maxdis;i++)
                //循环遍历加油站路径找寻耗油量最小值的站,满足耗油量小于maxDis 
                {
                    if(st[i].price < priceMin)//priceMin记录最低油价 
                    {
                        priceMin = st[i].price;
                        k = i;
                        if(st[cur_station].price > priceMin)//若找寻加油站价格比当前还低,则直接开车去,循环中断 
                        {
                            break; 
                        }
                    } 
                } 
                if(k == -1) break;//未经过遍历循环,则无法到达下一站,直接输出最大花费即可
                double need = (st[k].distance - st[cur_station].distance)/Davg;//计算从当前站到k站所需油量 
                //**如果当前站的油价比k站的高,我们就加正好到k站的油量need
                if(priceMin < st[cur_station].price)
                {
                    if(cur_oil < need)//当前油无法到达k,则加到刚好够 
                    {
                        sumprice += (need - cur_oil)* st[cur_station].price;
                        cur_oil = 0;//到k剩油 
                    }
                    else//若足够,到k油量即为原本油量减去到k所耗费的油 
                    {
                        cur_oil -= need;
                    }
                }
                //**否则当前站油价较低,则在当前站加满油 
                else
                {
                    sumprice += (Cmax - cur_oil) * st[cur_station].price;
                    cur_oil = Cmax - need;//到k剩油 
                } 
                cur_station = k;
            }
            if(cur_station == N)
            {
                printf("%.2f\n",sumprice);  
            } 
            else
            {
                printf("The maximum travel distance = %.2f\n",maxdis + st[cur_station].distance);
            }
        }
        return 0;
    } 
    

    参考链接:https://blog.csdn.net/ActionBeam/article/details/88411842

    2132-ProblemD-Repair the Wall

    来自 http://codeup.cn/contest.php?cid=100000584
    题析:

    //2132 ProblemD Repair the Wall
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    bool cmp(int a,int b)
    {
        return a>b;
    }
    
    int main()
    {
        int block[605]={0};
        int l,n,need,i;
        while(scanf("%d%d",&l,&n) != EOF)
        {
            for(i=0;i<n;i++)
            {
                scanf("%d",&block[i]);
            }
            sort(block,block+n,cmp);//将填充块从大到小排列
            need=l;
            for(i=0;i<n;i++)//裂缝所需减去填充块 
            {
                need -= block[i];
                if(need<=0) break;
            }
            if(need>0)//若need仍大于0,说明填充块不够 
            {
                printf("impossible\n");
            }
            else
            {
                printf("%d\n",i+1);
            }
        }
        return 0;
    }
    

    2134-ProblemE-FatMouse's Trade

    来自 http://codeup.cn/contest.php?cid=100000584
    题析:

    //2134 Problem  E        FatMouse's Trade
    //2134 Problem  E   FatMouse's Trade
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    typedef struct room_i
    {
        double J;//J[i]javaBean
        double F;//需要F[i]猫粮 
    };
    bool cmp(room_i a,room_i b)//按照需要猫粮与获得豆子比值从小到大排列 
    {
        return (a.F/a.J)<(b.F/b.J);
    }
    
    int main()
    {
        int M,N;
        while(cin>>M>>N&&M!=-1&&N!=-1)
        {
            struct room_i room[N];
            for(int i=0;i<N;i++)
            {
                cin>>room[i].J>>room[i].F;  
            }   
            sort(room,room+N,cmp);
            double res=0.00;
            for(int i=0;i<N;i++)
            {
                if(M>room[i].F)//如果猫粮满足守卫需求,则拿到所有豆子 
                {
                    res += room[i].J; 
                    M -= room[i].F;
                }
                else//若不满足守卫要求,按照比例拿豆子,并退出循环 
                {
                    res += room[i].J*(M/room[i].F);
                    break;
                }
            }
            printf("%.3f\n",res);
        } 
        return 0;
    }
    

    2143-ProblemF-迷瘴

    来自 http://codeup.cn/contest.php?cid=100000584
    题析:

    //2143 Problem  F   迷瘴
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    bool cmp(int a,int b)//按照从小到大排列 
    {
        return a<b;
    }
    
    int main()
    {
        int C;
        while(cin>>C)
        {
            while(C--)
            {//n种浓度的万能药水,体积V都相同,浓度不大于 W%
                int n,V,W;
                cin>>n>>V>>W;
                int P[n]={0};
                  
                for(int i=0;i<n;i++)//表示n种药水的浓度Pi%
                {
                    cin>>P[i];
                }
                sort(P,P+n,cmp);
                int res_V=V; double res_P=P[0];
                if(P[0]>W)//最低浓度不满足,则无法配置合格药水 
                {
                    res_V=0;res_P=0.00;
                }
                else
                {
                    for(int i=1;i<n;i++)
                    {
                        if((res_P*res_V+P[i]*V)/(res_V+V) <= W)//若预加入下一瓶药仍按满足,则混合下一瓶药 
                        {
                            res_P = (res_P*res_V+P[i]*V)/(res_V+V);
                            res_V += V;
                        }
                        else break;
                    }
                }
                printf("%d %.2f\n",res_V,res_P/100);
            }
            
            
        } 
        return 0;
    }
    

    5038-ProblemG-找零钱

    来自 http://codeup.cn/contest.php?cid=100000584
    题析:

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    using namespace std;
    int money[5]={50,20,10,5,1};//从大面值往小面值分配
     
    int main()
    {
        int n,x;
        while(scanf("%d",&n) != EOF)
        {
            for(int i=0;i<5;i++)
            {
                x=n/money[i];//x为每个面值对应的数量
                if(x)
                {
                    printf("%d*%d",money[i],x);//每种面值钞票及其数量输出
                    n=n%money[i];//余额,下一面值分配用
                    if(n)//未分配完,需要连接下一面额的“+”
                    {
                        printf("+");
                    }
                }
            }
            printf("\n");
        }
        return 0;
    }
     
    

    相关文章

      网友评论

        本文标题:《算法笔记》4.4小节——算法初步->贪心

        本文链接:https://www.haomeiwen.com/subject/dcuzphtx.html