这套题包含了历年真题，十分重要！！！！要考试的同学可以参考一下！！
此套题限时3小时。
A. C05.L08.贪心算法入门（一）.课堂练习1.书架(SSOI2017五年级t6)
- 传统题1000ms256MiB
题目描述
为了方便同学们查阅资料，程序设计兴趣小组的辅导老师打算将积攒了很多年的 n 本书放到上课教室的书架上去。
教室的书架是一层一层叠起来的，每一层最多可以放 m 本书。每一层的高度由放在这层中最高的那本书决定的，如果不放书，则认为这层的高度为 0 。为了使每个同学能方便地拿到想要的书，书架的总高度应尽可能低。请编程计算将这 n 本书放在书架上后书架的最小总高度，计算的过程中不考虑书的厚度与书架本身材料的厚度。
输入格式
共 n+1 行。
第 1 行 2 个整数 n 和 m ( 1 ≤ m ≤ n ≤ 100000 ) 。
接下来 n 行， 每行 1 个正整数， 分别表示每本书的高度( 每本书的高度不超过 100 )。
输出格式
一个整数，表示将 n 本书放入书架后书架的最小总高度。
样例
输入数据 1
3 2
20 10 30
输出数据 1
40
样例解释
将高度是 30 和 20 的两本书放在一层，则这层的高度为 30 ，将高度是 10 的那本书放在另外一层，则这层的高度为 10 ，则书架的总高度为 40 ，满足最小。
代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100005],s;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=n;i>=0;i-=m)
{
s=s+a[i];
}
cout<<s;
return 0;
}B. C05.L08.贪心算法入门（一）.课堂练习2礼物
- 传统题1000ms256MiB
题目描述
国庆马上要到了。小明喜欢的礼物有 n 种分别是：公仔、电子手表、漫画书等。
每种礼物有一件，每种礼物价钱都不一样。小明手头上有 m 元。
小明最多可以买多少件礼物？
输入格式
第一行，两个整数： n , m ( 1 <= n<=100 , 1 <= m <= 100000 )。
第二行， n 个空格分开的整数( 每个整数 <= 1000 )，代表每种礼物的价钱。
输出格式
一个整数，小明能买多少件礼物。
样例
输入数据 1
3 100
40 70 50
输出数据 1
2代码
#include<bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin>>n>>m;
vector<int>a(n);
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a.begin(),a.end());
int o=0;
int t=0;
for(int i=0;i<n;i++)
{
if(t+a[i]<=m)
{
t+=a[i];
o++;
}
else
{
break;
}
}
cout<<o;
return 0;
}C. C05.L08.贪心算法入门（一）.课堂练习3.数字圈(DLOI2019t4)
- 传统题1000ms256MiB
题目描述
当我们写数字时会发现有些数字有封闭区域，有的数字没有封闭区域。
数字 0 有一个封闭区域，数字 1、2、 3 都没有封闭区域，数字 4 有一个封闭区域，数字 5 没有封闭区域，数字 6 有一个封闭区域，数字 7 没有 封闭区域，数字 8 有两个封闭区域，数字 9 有一个封闭区域。
现在你要构造一个最小的非负整数，使得它的各位数字的封闭区域的数量加起来的总和恰好等于 K。
输入格式
一个整数 K ( 1 <= K <= 2500 )
输出格式
满足题意的最小的非负整数。
样例
输入数据 1
40
输出数据 1
88888888888888888888
输入数据 2
1
输出数据 2
0
输入数据 3
2
输出数据 3
8代码
#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;
}D. C05.L08.贪心算法入门（一）.课堂练习4.危险的实验(NHOI2015初中)
- 传统题1000ms256MiB
题目描述
小明最近在上化学课，他需要使用到 n 种化学物质来进行他的实验。在做实验的时候，他需要将所有化学物质放在桌面上，按次序排成一条直线。
然而每一种化学物质都是危险品，对于第 i 个化学物质，如果有另外一个化学物质距离它的距离小于 a_iai，那么就会发生爆炸。
小明想知道如果要安全的完成他的实验，桌子最短可以多短。
输入格式
第一行一个整数 n ，表示化学物质的个数。
第二行有 n 个整数，第 i 个整数 a_iai 表示第 i 个化学物质必须与其他化学物质保持的距离。
数据范围
20% 的数据 , 1 <= n <= 20
50% 的数据 , 1 <= n<= 100000
100% 的数据 , 1 <= n <= 1000000 , 1 <= a_iai <= 100000
输出格式
一个整数，表示能够让小明安全完成实验的桌子最小长度。
注意：物品要安原来的次序摆放。
样例
输入数据 1
3
3 1 2
输出数据 1
5代码
#include<bits/stdc++.h>
using namespace std;
long long n,a[10000001],o=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
o=o+max(a[i],a[i+1]);
}
cout<<o;
return 0;
}E. C05.L08.贪心算法入门（一）.课堂练习5.最大步数(GCOI2019六年级t2)
- 传统题1000ms256MiB
题目描述
给出了两个非负整数 P 和 Q。您的任务是使得 P 和 Q 相等。在每一步中，您可以执行以 下两项操作之一： 1、将任何质数加到 P 上。 2、从 Q 减去任何质数。 如果不可能使 P 和 Q 相等，则输出 -1 。否则，输出一个非负整数：可以执行的最大步数。
输入格式
数字 0 和 1 不是质数。
输出格式
一行，两个整数 P 和 Q。 0 <= P, Q <= 10^18
样例
输入数据 1
5 9
输出数据 1
2
输入数据 2
5 10
输出数据 2
2
输入数据 3
5 6
输出数据 3
-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;
}F. C05.L08.贪心算法入门（一）.课堂练习6.渡河(GCOI2019六年级t4)
- 传统题1000ms256MiB
题目描述
总共有 X 人要坐船过河。
一个小船最多可以坐 4 人，一个小船固定收费 32 元。
一个大船最多可以坐 6 人，一个大船固定收费 36 元。
码头有无穷多小船和大船。
问如何坐船，才能使得总费用最小。
输入格式
一个整数 X。
数据范围
60% 的数据, 1 <= X <= 1000
80% 的数据, 1 <= X <= 1000000
100% 的数据, 1 <= X <= 2000000000
输出格式
一个整数，表示最小的总费用。
样例
输入数据 1
4
输出数据 1
32
输入数据 2
12
输出数据 2
72代码
#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;
}谢谢欢看！！！！