当前位置：首页 > news >正文

贪心算法入门（一）

news 来源：原创 2025/5/15 4:16:21

第1题礼物查看测评数据信息

国庆马上要到了。小明喜欢的礼物有n种分别是：公仔、电子手表、漫画书等。

每种礼物有一件，每种礼物价钱都不一样。小明手头上有 m 元。

小明最多可以买多少件礼物？

输入格式

第一行，两个整数：n，m 1 <= n<=100,1<=m<= 100000。

第二行，n个空格分开的整数(每个整数<=1000)，代表每种礼物的价钱。

输出格式

一个整数，小明能买多少件礼物。

输入/输出例子1

输入：

3 100

40 70 50

输出：

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[999999],ans,s=0;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++){ans+=a[i];if(ans>m)break;else s++;}cout<<s;return 0;
}

第2题书架（SSOI2017五）查看测评数据信息

为了方便同学们查阅资料，程序设计兴趣小组的辅导老师打算将积攒了很多年的n本书放到上课教室的书架上去。

教室的书架是一层一层叠起来的，每一层最多可以放m本书。每一层的高度由放在这层中最高的那本书决定的，如果不放书，则认为这层的高度为0。为了使每个同学能方便地拿到想要的书，书架的总高度应尽可能低。请编程计算将这n本书放在书架上后书架的最小总高度，计算的过程中不考虑书的厚度与书架本身材料的厚度。

输入格式

输入共n+1行。

第1行2个整数n和m (1≤m≤n≤100000) 。

接下来n行，每行1个正整数，分别表示每本书的高度(每本书的高度不超过100)。

输出格式

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

输入/输出例子1

输入：

3 2 
20 10 30

输出：

样例解释

【样例解释】

将高度是30和20的两本书放在一层，则这层的高度为30，将高度是10的那本书放在另外一层，则这层的高度为10，则书架的总高度为40，满足最小。

#include<bits/stdc++.h>
using namespace std;
bool cmp(int x,int y){return x>y;
}
int n,m,a[1000005],s=0;
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i+=m){s+=a[i];}cout<<s;return 0;
}

第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

输入：

15 40 22

1 3 1

1 1234 3000

输出：

-1

第4题数字圈（DLOI2019XJ4）查看测评数据信息

当我们写数字时会发现有些数字有封闭区域，有的数字没有封闭区域。数字 0 有一个封闭区域，数字 1、 2、3 都没有封闭区域，数字 4 有一个封闭区域，数字 5 没有封闭区域，数字 6 有一个封闭区域，数字 7 没有

封闭区域，数字 8 有两个封闭区域，数字 9 有一个封闭区域。

现在你要构造一个最小的非负整数，使得它的各位数字的封闭区域的数量加起来的总和恰好等于 K。

输入格式

一个整数 K。 1 <= K <= 2500。

输出格式

满足题意的最小的非负整数。

输入/输出例子1

输入：

输出：

输入/输出例子2

输入：

输出：

输入/输出例子3

输入：

输出：

88888888888888888888

#include<bits/stdc++.h>
using namespace std;
int k;
int main(){cin>>k;if(k==1){cout<<0;return 0;}if(k%2==1){cout<<"4";for(int i=1;i<=k/2;i++){cout<<"8";}}else{for(int i=1;i<=k/2;i++){cout<<"8";}}return 0;
}

第5题危险的实验(nhoi2015初中组) 查看测评数据信息

小明最近在上化学课，他需要使用到 n 种化学物质来进行他的实验。在做实验的时候，他需要将所有化学物质放在桌面上，按次序排成一条直线。
然而每一种化学物质都是危险品，对于第 i个化学物质，如果有另外一个化学物质距离它的距离小于ai，那么就会发生爆炸。
小明想知道如果要安全的完成他的实验，桌子最短可以多短。

输入格式

第一行一个整数n，表示化学物质的个数。
第二行有n个整数，第i个整数ai表示第i个化学物质必须与其他化学物质保持的距离。

输出格式

输出一行，包括一个整数，表示能够让小明安全完成实验的桌子最小长度。
注意：物品要安原来的次序摆放。

输入/输出例子1

输入：

3
3 1 2

输出：

样例解释

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

#include<bits/stdc++.h>
using namespace std;
long long n,a[999999],s,t;
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<n;i++){t=max(a[i],a[i+1]);s+=t;}cout<<s;return 0;
}

第6题最大步数（gcoi2019小学甲组第二题）查看测评数据信息

给出了两个非负整数 P 和 Q。您的任务是使得 P 和 Q 相等。在每一步中，您可以执行以下两项操作之一：

1、将任何质数加到 P 上。

2、从 Q 减去任何质数。

如果不可能使 P 和 Q 相等，则输出-1。否则，输出一个非负整数：可以执行的最大步数。

输入格式

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

输出格式

一个整数。

输入/输出例子1

输入：

5 9

输出：

输入/输出例子2

输入：

5 10

输出：

输入/输出例子3

输入：

5 6

输出：

-1

样例解释

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

#include<bits/stdc++.h>
using namespace std;
long long p,q;
int main(){cin>>p>>q;if(p>q){cout<<-1;return 0;}if(p-q==0){cout<<0;return 0;}if(p-q==1){cout<<-1;return 0;}cout<<(q-p)/2;return 0;
}

第7题渡河查看测评数据信息

总共有 X 人要坐船过河。

一个小船最多可以坐 4 人，一个小船固定收费 32 元。

一个大船最多可以坐 6 人，一个大船固定收费 36 元。

码头有无穷多小船和大船。

问如何坐船，才能使得总费用最小。

输入格式

一个整数 X。

60%的数据, 1 <= X <= 1000

80%的数据，1 <= X <= 1000000

100 的数据，1 <= X <= 2000000000

输出格式

一个整数，表示最小的总费用。

输入/输出例子1

输入：

输出：

输入/输出例子2

输入：

输出：

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

第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

输入：

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

输出：

70
77
177177
999999999000000000
999999999
55
10

#include<bits/stdc++.h>
using namespace std;
long long t,n,a,b,x,y,m,c,d,a1,b1,m1;
int main(){cin>>n;t=n;while(t--){cin>>a>>b>>x>>y>>m;a1=a,b1=b,m1=m;if(m>a-x)m-=a-x,a=x;else a-=m,m=0;if(m>b-y)b=y;else b-=m;if(m1>=b1-y)m1-=b1-y,b1=y;	else b1-=m1,m1=0;if(m1>a1-x)a1=x;else a1-=m1;c=a*b,d=a1*b1;if(c>d)cout<<d;else cout<<c;if(n!=t)cout<<'\n'; }return 0;
}

第9题蜡烛(nhoi2010pj) 查看测评数据信息

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

输入格式

第一行：一个整数n, 1 <= n <= 50.

第二行：n个整数，第i个整数表示第i根蜡烛的长度h[i]. 1 <= h[i] <= 100.

输出格式

一个整数，总共最多能用多少个晚上。

输入/输出例子1

输入：

2 2 2

输出：

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],s,g;
bool cmp(int a,int b){return a>b;
}
int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){g=0;s++;for(int j=1;j<=i;j++){if(a[j]==0){ cout<<s-1;return 0;}a[j]--;}sort(a+1,a+1+n,cmp);}cout<<s;return 0;
}

输入格式

输出格式

输入/输出例子1

输入格式

输出格式

输入/输出例子1

样例解释

输入格式

输出格式

输入/输出例子1

输入/输出例子2

输入格式

输出格式

输入/输出例子1

输入/输出例子2

输入/输出例子3

输入格式

输出格式

输入/输出例子1

样例解释

输入格式

输出格式

输入/输出例子1

输入/输出例子2

输入/输出例子3

样例解释

输入格式

输出格式

输入/输出例子1

输入/输出例子2

输入格式

输出格式

输入/输出例子1

输入格式

输出格式

输入/输出例子1

相关文章：