贪心算法总结
问题 A: 和最大
题目描述
对于一个N\times M的正整数矩阵，在每一行中选择一个数值，并使所选的所有数值之和达到最大值。
已知1< =N< =10, 1< =M< =10
输入
输入数据有多行，第一行是矩阵的行数N和列数M
接下来的N行M列为输入数据（正整数，不超过10000）
输出
输出N行元素和的最大值。
样例输入
3 3
1 2 3
4 5 6
7 8 9样例输出
18代码
#include <stdio.h>
int main(int argc, char** argv) {
int arr[100];
int a,b;
int i,j;
int res = 0;
scanf("%d %d",&a,&b);
for(i=0; i<a; i++){
int max = 0;
for(j=0;j<b;j++){
scanf("%d",&arr[i]);
if(max < arr[i]){
max = arr[i];
}
}
res += max;
}
printf("%d",res);
return 0;
}问题 B: 分牌
题目描述
共有N堆纸牌分别编号为1至N。每堆纸牌的数量各不相同，并且总的数量必须正好是N的倍数。允许从任何一堆中移取一定数量的卡片，并将其转移到另一堆中进行操作。
移牌规则如下：从标记为1的堆积中取出的所有纸牌必须移至标记为2的位置；位于标记为N（最大值）堆积中的所有纸牌必须移至标记为N-1的位置；其余各堆积取出的所有纸片可随意移至相邻两侧任一位置。
为了实现每堆纸牌数量一致的目标,确定一种移动方法,并使用最少的移动次数来完成任务
例如 N=4，4 堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6
移动3次可达到目的：
从 ③ 取4张牌放到④（9 8 13 10）->从③取3张牌放到 ②（9 11 10 10）-> 从②取1张牌放到①（10 10 10 10）。
输入
N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
输出
所有堆均达到相等时的最少移动次数。
样例输入
4
9 8 17 6 样例输出
3代码
#include <stdio.h>
#include <stdlib.h>
int main() {
int avg=0,i,n,a[100],step=0,j;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&a[i]);
avg+=a[i];
}
avg/=n;
for(i=0;i<n;i++)
a[i]-=avg;
i=0;j=n;
while(a[i]==0&&i<n) ++i;
while(a[j]==0&&j>0) --j;
while(i<j){
a[i+1]+=a[i];
a[i]=0;
++step;
++i;
while(a[i]==0&&i<j)
++i;
}
printf("%d",step);
return 0;
}问题 C: 活动选择
题目描述
近期内有多达n项校园活动中需要用到学校的大型礼堂，并非所有项目都能同时顺利开展，在同一时间段内该礼堂的场地资源也只能供一个项目团队利用。因部分校园项目的具体实施时间节点存在重叠或冲突情况, 学校行政人员不得不将部分原本计划在此处进行的项目转移至其他教室开展教学工作
现提供n个活动在礼堂的时间段bi至ei（bi < ei且ei≤32767），希望组织办公室人员合理安排这些活动以充分利用礼堂。
输入
在第一行输入一个整数n（其中n不超过1000）。之后的每一行将包含两个整数bi和ei（其中bi必须小于ei），并且满足ei不超过32767的条件。
输出
输出最多能安排的活动个数
样例输入
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13样例输出
4代码
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
int i,j,n,temp_b,temp_e;
int begin[1000],end[1000];
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&begin[i]);
scanf("%d",&end[i]);
}
// 选择排序
for (i = 0 ; i < n - 1 ; i++){
int k = i;
for (j = i + 1; j < n; j++)
if (end[j] < end[k])
k = j;
if(k!=i){
temp_b= begin[i];
temp_e = end[i];
begin[i]=begin[k];
end[i]=end[k];
begin[k]=temp_b;
end[k]=temp_e;
}
}
for (i = 0 ; i < n; i++){
cout << begin[i] << " " << end[i] << endl;
}
// res 表示选取节目个数 t 表示结束时间
int t=-1,res=0;
for(i=0;i<n;i++){
// 如果开始时间比上一个结束时间大，则该节目是可以进节目单的
if(begin[i] >= t){
// 计数累加
++res;
// 在把选择的节目的结束时间保存用于下一次比较
t=end[i];
}
}
printf("%d",res);
return 0;
}问题 D: 删数问题
题目描述
给定一个由大量位数组成的高精度正整数N，在其内部删除其中任意S位数字后剩余的各位数字仍按原有顺序排列形成一个新的正整数M。编写程序对于给定的N和S值而言寻求一种方法使得所剩各位数字组成的数值M达到最小
输出新的正整数。（N不超过240位）输入数据均不需判错。
输入
n
s
输出
最后剩下的最小数。
样例输入
175438
4
样例输出
13
代码
#include <iostream>
#include <string.h>
using namespace std;
int main(int argc, char** argv) {
int i,j,n,lenc,lens,index=0;
char nums[240];
scanf("%s\n",nums);
scanf("%d",&n);
lens = strlen(nums);
lenc=lens;
for(i=0;i<n;i++){
for(j=0;j<lens-1;j++){
if(nums[j]>nums[j+1]){
for(int k=j;k<lens-1;k++)
nums[k]=nums[k+1];
break;
}
}
--lens;
}
for(j=0;j<lens;j++){
cout << nums[j];
}
return 0;
}问题 E: 便利店
题目描述
天宝驱车前往便利店，并打算购买一些饮料。在便利店内出售的瓶装饮料种类繁多，在不同规格的瓶子中售价各异：一瓶容量为0.25升的售价为A元；一瓶容量为0.5升售价B元；而1升容量则以C元标价；2升容量则售价D元。在便利店里销售的所有瓶装饮料均无限制供应。
她要购买N升的饮料，最少需要花费多少钱？智慧的你能编写一个程序帮她计算一下吗？
已知
1） 1≤A,B,C,D≤108 ，1≤N≤109
2） 输入的数据都是整数
输入
输入数据按照下面格式
A B C D
N
输出
输出天宝要买N升的饮料所需要花的钱最小值。
样例输入
20 30 70 90
3
样例输出
150
提示
买1瓶2升的饮料和2瓶0.5升的饮料。 这样正好可以买到3升饮料，花费是 90+30+30=150 元。
代码
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
long long a,b,c,d,n;
cin>>a>>b>>c>>d;
cin>>n;
long long min1=min(min(a*4,b*2),c);
long long min2=min(min1*2,d);
long sum=n/2*min2+n%2*min1;
cout<<sum<<endl;
//cout<<1ll*n/2*min2+1ll*n%2*min1<<endl;
}问题 F: 节目安排
题目描述
假期到啦！天宝终于有时间放松心情地追剧了。
但是天宝非常喜欢看很多节目，
请问您能否帮他最大限度地合理规划观看时间，
让他完整地收看所有他感兴趣的节目？
麻烦您提供详细的时间表，
希望他能顺利享受追剧的乐趣！
输入
测试数据有多组。
每一组测试的第一行都是一个整数n（不大于100），它代表天宝喜欢观看节目的总数。
接下来会有多个部分（具体数目由前面的值决定），每个部分包括两个整数s_i和e_i。
当数值n等于零时，则表示测试数据结束。
输出
对于每组输入，输出能完整看到的电视节目的个数。
样例输入
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0样例输出
5代码
#include <cstdio>
#include <algorithm>
using namespace std;
struct node
{
int start;
int end;
}a[100];
int compare(node a,node b)
{
return a.end<b.end;
}
int main()
{
int n,i,f,flag;
while(scanf("%d",&n)&&n)
{
f=1;
for(i=0;i<n;i++)
{
scanf("%d%d",&a[i].start,&a[i].end);
}
sort(a,a+n,compare);
flag=a[0].end;
for(i=1;i<n;i++)
{
if(a[i].start>=flag)
{
f++;
flag=a[i].end;
}
}
printf("%d\n",f);
}
}问题 G: 最大整数
题目描述
设有n个正整數（其中n≤20），將它們排列組合並连接起來以形成一個最大的多數位數字串。例如：當n=3時，將三个數值為13、312和343的數按最優的方式排列後得到的最大多數位數字串為：7\cdot 8 + 9；又如：當n=4時，则四个數值為7、19、5和8的數按最佳排序後得到的最大多數位字符串為 9\cdot (8\cdot (5\cdot 7 + 8) + 5) + ...
输入
以第一行为输入的开始，请注意以下几点：第一行包含一个正整数n；第二行包含n个正整数，并通过空格分隔
输出
输出n个数连接起来的最大整数
样例输入
3
13 312 343样例输出
34331213代码
#include <iostream>
#include<algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int cmp(string a,string b){
return a+b > b+a;
}
int main(int argc, char** argv) {
int n;
string a[20];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n,cmp);
for(int i=0;i<n;i++)
cout<<a[i];
return 0;
}问题 H: 导弹拦截
题目描述
该国有意针对敌国导弹攻击而研发了一种防空导弹系统；然而该系统的不足之处在于：尽管其第一枚弹道可以达到任何高度；但随后发射的每一枚导弹的高度均不得超过前一枚；某日雷达监测到敌国的一枚导弹正朝我国内部方向飞行；由于该系统仍处于试验阶段；因此一套这样的防空装置可能无法拦截全部 incoming missiles.
接收导弹依次飞来的高度数值（由雷达提供的数值均为不大于30,000的正整数）。确定最少数量的导弹拦截系统配置……使得能够有效覆盖所有 incoming missile heights within the specified range。
输入
n颗依次飞来的高度（1≤n≤1000）
输出
要拦截所有导弹最小配备的系统数k
样例输入
389 207 155 300 299 170 158 65样例输出
2提示
输入：导弹高度： 7 9 6 8 5
输出：导弹拦截系统K=2
输入：导弹高度： 4 3 2
输出：导弹拦截系统K=1
代码
#include <iostream>
#include<cstring>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
int a[1000];//存储导弹飞来的高度
int b[1000];//存储本系统当前所能拦截的最低高度，数组下标表示本系统的序号
// 7 9 6 8 5
int n=1;
while(cin>>a[n]){
n++;
}
int p=0;//p用来记录能够拦截某导弹的系统的序号
//若没有系统能拦截，则p=0
int k=1;//拦截系统的数量或拦截系统的序号，初始化为1
b[k]=a[1];//第一个导弹的高度给第一个系统的最低拦截高度
for(int i=2;i<=n;i++){
p=0;
for(int j=1;j<=k;j++){ //遍历所有当前的系统，寻找能拦截该导弹的系统
if(b[j]>=a[i]){//找到了
if(p==0)
p=j;//标记该系统的序号
else if(b[p]>b[j])
p=j;//贪心算法的体现，在所有能拦截的系统中找拦截高度最低的系统来拦截该导弹
}
}
if(p==0){ //没找到
k++;//建立一个新的拦截系统
b[k]=a[i];
}
else//在找到的基础上更新那个系统的最低高度
b[p]=a[i];
}
cout<<k<<endl;
return 0;
}