贪默算法入门（一）

第1题     礼品 查看测评数据信息    国庆马上要到了。小明喜欢的礼品有n种分别是：公仔、电子手表、漫画书等。
  每种礼品有一件，每种礼品价钱都不一样。小明手头上有 m 元。
  小明最多可以买多少件礼品？
    输入格式

  
  第一行，两个整数：n，m   1 <= n<=100,1<=m<= 100000。
  第二行，n个空格分开的整数(每个整数<=1000)，代表每种礼品的价钱。 
  
    输出格式

  
  一个整数，小明能买多少件礼品。
  
    输入/输出例子1

  输入：
  3 100 
  40 70 50 
  
  输出：
  2

1. #include<bits/stdc++.h>
2. using namespace std;
3. long long n,m,a[999999],ans,s=0;
4. int main(){
5.     cin>>n>>m;
6.     for(int i=1;i<=n;i++)cin>>a[i];
7.     sort(a+1,a+1+n);
8.     for(int i=1;i<=n;i++){
9.         ans+=a[i];
10.         if(ans>m)break;
11.         else s++;
12.     }
13.     cout<<s;
14.     return 0;
15. }

复制代码

    第2题     书架（SSOI2017五） 查看测评数据信息       为了方便同学们查阅资料，程序计划兴趣小组的辅导老师打算将积攒了很多年的n本书放到上课教室的书架上去。
   教室的书架是一层一层叠起来的，每一层最多可以放m本书。每一层的高度由放在这层中最高的那本书决定的，如果不放书，则以为这层的高度为0。为了使每个同学能方便地拿到想要的书，书架的总高度应尽大概低。请编程计算将这n本书放在书架上后书架的最小总高度，计算的过程中不思量书的厚度与书架本身材料的厚度。
       输入格式

   
   输入共n+1行。
   第1行2个整数n和m (1≤m≤n≤100000) 。
   接下来n行，每行1个正整数，分别表现每本书的高度(每本书的高度不超过100)。
   
       输出格式

   
   输出共1行，表现将n本书放入书架后书架的最小总高度。
   
       输入/输出例子1

   输入：
  

1. 3 2 
2. 20 10 30

复制代码

  
   
   
   输出：
   40
   
       样例解释

   
   【样例解释】
   将高度是30和20的两本书放在一层，则这层的高度为30，将高度是10的那本书放在别的一层，则这层的高度为10，则书架的总高度为40，满足最小。
  

1. #include<bits/stdc++.h>
2. using namespace std;
3. bool cmp(int x,int y){
4.     return x>y;
5. }
6. int n,m,a[1000005],s=0;
7. int main(){
8.     cin>>n>>m;
9.     for(int i=1;i<=n;i++){
10.             cin>>a[i];
11.     }
12.     sort(a+1,a+1+n,cmp);
13.     for(int i=1;i<=n;i+=m){
14.             s+=a[i];
15.     }
16.     cout<<s;
17.     return 0;
18. }

复制代码

      第3题     吃苹果 查看测评数据信息          连小朋侪都知道，呆毛王Saber喜欢吃苹果。现在Saber有三箱苹果。第一个箱子里有n1个苹果，第二箱有n2个，第三箱有n3个。Saber是个吃货，但也是个爱美的女生。三箱苹果这样看起来更悦目：
      第一点就是每个箱子都不能空。
      第二点就是苹果数量应该是递增的。也就是说，第一个箱子的苹果数少于第二个箱子，第二箱的苹果少于第三箱。
      Saber今天有些饱，所以想通过吃尽量少的苹果同时满足以上两个要求而使箱子看上去更美。请你输出Saber吃掉的最少的苹果数量。
      如果她无法完成心愿就输出-1吧。
          输入格式

   
    第一行，一个正整数nG，表现数据的组数，nG<=5
接下来nG行，每行三个正整数，依次代表n1，n2，n3，其中1<=n1,n2,n3<=3000
   
          输出格式

   
    nG行，每行一个整数，即标题要求的答案。
   
          输入/输出例子1

    输入：
    输出：
          输入/输出例子2

    输入：
    3
    15 40 22
    1 3 1
    1 1234 3000
   
   
    输出：
    19
    -1
    0
         第4题     数字圈（DLOI2019XJ4） 查看测评数据信息             当我们写数字时会发现有些数字有封闭区域， 有的数字没有封闭区域。 数字 0 有一个封闭区域， 数字 1、 2、3 都没有封闭区域， 数字 4 有一个封闭区域， 数字 5 没有封闭区域， 数字 6 有一个封闭区域， 数字 7 没有
     封闭区域， 数字 8 有两个封闭区域， 数字 9 有一个封闭区域。
     现在你要构造一个最小的非负整数， 使得它的各位数字的封闭区域的数量加起来的总和恰恰等于 K。
             输入格式

     
     一个整数 K。 1 <= K <= 2500。
     
             输出格式

     
     满足题意的最小的非负整数。
     
             输入/输出例子1

     输入：
     1
     
     输出：
     0
     
             输入/输出例子2

     输入：
     2
     
     输出：
     8
     
             输入/输出例子3

     输入：
     40
     
     输出：
   

1. 88888888888888888888

复制代码

   

1. #include<bits/stdc++.h>
2. using namespace std;
3. int k;
4. int main(){
5.     cin>>k;
6.     if(k==1){
7.         cout<<0;
8.         return 0;
9.     }
10.     if(k%2==1){
11.         cout<<"4";
12.         for(int i=1;i<=k/2;i++){
13.             cout<<"8";
14.         }
15.     }
16.     else{
17.         for(int i=1;i<=k/2;i++){
18.             cout<<"8";
19.         }
20.     }
21.     return 0;
22. }

复制代码

          第5题     伤害的实行(nhoi2015初中组) 查看测评数据信息                小明最近在上化学课，他必要使用到 n 种化学物质来举行他的实行。在做实行的时间， 他必要将全部化学物质放在桌面上，按次序排成一条直线。 
然而每一种化学物质都是伤害品，对于第 i个化学物质，如果有别的一个化学物质间隔它的间隔小于ai，那么就会发生爆炸。 
小明想知道如果要安全的完成他的实行，桌子最短可以多短。 
                输入格式

      
      第一行一个整数n，表现化学物质的个数。 
第二行有n个整数，第i个整数ai表现第i个化学物质必须与其他化学物质保持的间隔。
      
                输出格式

      
      输出一行，包括一个整数，表现可以或许让小明安全完成实行的桌子最小长度。 
留意：物品要安原来的次序摆放。 
      
                输入/输出例子1

      输入：
      3 
3 1 2
      
      输出：
      5
      
                样例解释

      
      数据范围 
20%的数据，1<=n<=20 
50%的数据，1<=n<=100000 
100%的数据，1<=n<=1000000，1<=ai<=100000
     

1. #include<bits/stdc++.h>
2. using namespace std;
3. long long n,a[999999],s,t;
4. int main(){
5.     cin>>n;
6.     for(int i=1;i<=n;i++){
7.         cin>>a[i];
8.     }
9.     for(int i=1;i<n;i++){
10.         t=max(a[i],a[i+1]);
11.         s+=t;
12.     }
13.     cout<<s;
14.     return 0;
15. }

复制代码

            第6题     最大步数（gcoi2019小学甲组第二题） 查看测评数据信息                   给出了两个非负整数 P 和 Q。您的任务是使得 P 和 Q 相等。在每一步中，您可以执行以下两项操作之一：
       1、将任何质数加到 P 上。
       2、从 Q 减去任何质数。
       如果不大概使 P 和 Q 相等，则输出-1。否则，输出一个非负整数：可以执行的最大步数。
                   输入格式

      
       一行，两个整数 P 和 Q。 0 <= P,Q <= 10^18
      
                   输出格式

      
       一个整数。
      
                   输入/输出例子1

       输入：
       5 9
      
       输出：
       2
      
                   输入/输出例子2

       输入：
       5 10    
      
       输出：
       2
      
                   输入/输出例子3

       输入：
       5 6
      
       输出：
       -1
      
                   样例解释

      
       友情提示：数字0和1不是质数
      

1. #include<bits/stdc++.h>
2. using namespace std;
3. long long p,q;
4. int main(){
5.     cin>>p>>q;
6.     if(p>q){
7.         cout<<-1;
8.         return 0;
9.     }
10.     if(p-q==0){
11.         cout<<0;
12.         return 0;
13.     }
14.     if(p-q==1){
15.         cout<<-1;
16.         return 0;
17.     }
18.     cout<<(q-p)/2;
19.     return 0;
20. }

复制代码

              第7题     渡河 查看测评数据信息                      统共有 X 人要坐船过河。
        一个小船最多可以坐 4 人，一个小船固定收费 32 元。
        一个大船最多可以坐 6 人，一个大船固定收费 36 元。
        码头有无穷多小船和大船。
        问如何坐船，才能使得总费用最小。
        
                      输入格式

        
        一个整数 X。
        60%的数据, 1 <= X <= 1000
        80%的数据，1 <= X <= 1000000
        100 的数据，1 <= X <= 2000000000
        
                      输出格式

        
        一个整数，表现最小的总费用。
        
                      输入/输出例子1

        输入：
        4
        
        输出：
        32
        
                      输入/输出例子2

        输入：
        12
        
        输出：
        72
      

1. #include<bits/stdc++.h>
2. using namespace std;
3. long long x,s,l;
4. int main(){
5.     cin>>x;
6.     if(x<=4)s=32;
7.     else{
8.         s+=(x/6)*36;
9.         l=x%6;
10.         if(l==5)s+=36;
11.         if(l==4||l==3)s+=32;
12.         if(l==2||l==1)s+=28;
13.     }
14.     cout<<s;
15.     return 0;
16. }

复制代码

                第8题     最小乘积(NHOI2020xj4) 查看测评数据信息                         给定4个整数：a,b,x,y。刚开始a>=x，b>=y。你可以做如下操作不超过n次：
         每次你可以选择a或者b，然后让它的值减少1；不外你要保证本次操作之后a的值不能小于x且b的值不能小于y。
         问最多n次操作之后，a*b的最小值是多少？
         
                         输入格式

         
         多组测试数据。
         第一行，一个整数T，表现有T组测试数据。1<=T<=20000。
         接下来有T行，每行5个整数：a,b,x,y,n。1<=a,b,x,y,n<=10^9。
         
         
         
                         输出格式

         
         共T行，每行一个整数。
         
                         输入/输出例子1

         输入：
        

1. 7
2. 10 10 8 5 3
3. 12 8 8 7 2
4. 12343 43 4543 39 123212
5. 1000000000 1000000000 1 1 1
6. 1000000000 1000000000 1 1 1000000000
7. 10 11 2 1 5
8. 10 11 9 1 10

复制代码

        
         
         输出：
        

1. 70
2. 77
3. 177177
4. 999999999000000000
5. 999999999
6. 55
7. 10

复制代码

      

1. #include<bits/stdc++.h>
2. using namespace std;
3. long long t,n,a,b,x,y,m,c,d,a1,b1,m1;
4. int main(){
5.     cin>>n;
6.     t=n;
7.     while(t--){
8.             cin>>a>>b>>x>>y>>m;
9.             a1=a,b1=b,m1=m;
10.             if(m>a-x)m-=a-x,a=x;
11.                 else a-=m,m=0;
12.                 if(m>b-y)b=y;
13.                 else b-=m;
14.                 if(m1>=b1-y)m1-=b1-y,b1=y;       
15.                 else b1-=m1,m1=0;
16.                 if(m1>a1-x)a1=x;
17.                 else a1-=m1;
18.                 c=a*b,d=a1*b1;
19.                 if(c>d)cout<<d;
20.                 else cout<<c;
21.                 if(n!=t)cout<<'\n';
22.         }
23.     return 0;
24. }

复制代码

                  第9题     蜡烛(nhoi2010pj) 查看测评数据信息                            奶牛bessie有n根蜡烛，第i根蜡烛的长度是h. bessie最近刚上完小学，只会加减法。它想知道它的n根蜡烛最多能用多少个晚上。由于bessie比较胆小，因此它第一个晚上只点燃一根蜡烛，第二个晚上点燃两根蜡烛，第三个晚上点燃三根蜡烛…第i个晚上它必须要点燃i根蜡烛。每根被点燃的蜡烛,它燃烧一个晚上会使得它的长度减少1。一旦蜡烛的长度变成0，那么该根蜡烛就用完了。如果第i个晚上bessie发现不敷i根蜡烛用了,那么bessie就会睡不着。 Bessie想知道，它该如何选择每个晚上点燃哪些蜡烛，可以使得它的n根蜡烛能用尽量多的晚上。输出最多能用多少个晚上。
                            输入格式

         
          第一行：一个整数n, 1 <= n <= 50.
          第二行：n个整数，第i个整数表现第i根蜡烛的长度h. 1 <= h <= 100.
         
                            输出格式

         
          一个整数，统共最多能用多少个晚上。
         
                            输入/输出例子1

          输入：
          3
          2 2 2
         
         
         
          输出：
          3
         

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n,a[10005],s,g;
4. bool cmp(int a,int b){
5.         return a>b;
6. }
7. int main(){
8.         cin>>n;
9.         for(int i=1;i<=n;i++){
10.                 cin>>a[i];
11.         }
12.         sort(a+1,a+1+n,cmp);
13.         for(int i=1;i<=n;i++){
14.                 g=0;
15.                 s++;
16.                 for(int j=1;j<=i;j++){
17.                         if(a[j]==0){
18.                            cout<<s-1;
19.                            return 0;
20.                     }
21.                         a[j]--;
22.                 }
23.                 sort(a+1,a+1+n,cmp);
24.         }
25.         cout<<s;
26.         return 0;
27. }

复制代码

         
                                          

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。