算法笔记#3:几道经典的贪心算法补题

写在最前：

---

1001 渊子赛马

描述

赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。 
赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 
孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。 
比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。 
就是这么简单，现在渊子也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！），相同则算对手赢。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。渊子有N(1≤N≤1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看渊子能否赢得比赛。

输入

输入有多组测试数据。 
每组测试数据包括3行： 
第一行输入N(1≤N≤1000)。表示马的数量。 
第二行有N个整型数字，即渊子的N匹马的速度。 
第三行有N个整型数字，即对手的N匹马的速度。 
当N为0时退出。

输出

若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出“YES”。 
否则输出“NO”。

样例输入

5
2 3 3 4 5
1 2 3 4 5
4
2 2 1 2
2 2 3 1
0

样例输出

YES
NO

如果渊子最快的马比齐王快，那么用它来比

如果渊子最慢的马比齐王快，那么用它来比

不同于上面两种情况，先用渊子最慢的马和齐王最快的马比，先输一把，然后再用两者第二快的马进行比较，在比较过程中最外面的for循环就是用来控制比赛场次的。而已经比过赛的马通过数组的角标来控制。

开头的win，初始化为0，将渊子赢的小场记数。t_max,t_min,q_max,q_min这四个数据分别进行初始化，是为了接下来一个一个比较作了准备。如果齐王赢，进行下一轮一比较，将双方的角标加一，胜利的次数加一；如果渊子最小的马速度小于齐王，则隐形的将渊子速度最小的马与齐王速度最大的马进行比较，放弃一把，将田忌角标加一，齐王角标减一。以此类推，注意研究选择结构的每个条件。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define maxn 1001
4.  
   int main ()
5.  
   {
6.  
   int n,i,a[maxn],b[maxn],t_max,t_min,q_max,q_min,win,j,k ;
7.  
   double h;
8.  
   while(scanf("%d",&n)!=EOF&&n!=0)
9.  
   {
10.  
    for(i=0;i<n;i )
11.  
    {
12.  
    cin>>a[i];
13.  
     
14.  
    }
15.  
    for(i=0;i<n;i )
16.  
    {
17.  
    cin>>b[i];
18.  
     
19.  
    }
20.  
     
21.  
    sort(a,a n);
22.  
    sort(b,b n);
23.  
    t_max=n-1 ;
24.  
    t_min=0;
25.  
    q_max=n-1;
26.  
    q_min=0;
27.  
     
28.  
     
29.  
    win=0;
30.  
     
31.  
    for (i=0;i<n;i )
32.  
    {
33.  
     
34.  
     
35.  
    if (a[t_min]>b[q_min])
36.  
    {
37.  
    t_min ;
38.  
    q_min ;
39.  
    win ;
40.  
    }
41.  
     
42.  
    else if (a[t_min]<b[q_min])
43.  
    {
44.  
    t_min ;
45.  
    q_max--;
46.  
    }
47.  
    else
48.  
    {
49.  
     
50.  
    if (a[t_max]>b[q_max])
51.  
    {
52.  
    t_max--;
53.  
    q_max--;
54.  
    win ;
55.  
    }
56.  
    else if (a[t_max]<b[q_max])
57.  
    {
58.  
    q_max--;
59.  
    t_min ;
60.  
    }
61.  
     
62.  
    else
63.  
    {
64.  
    if (a[t_min]<a[q_max])
65.  
    {
66.  
    t_min ;
67.  
    q_max--;
68.  
    }
69.  
    }
70.  
    }
71.  
    }
72.  
    h=n/2;
73.  
    if(win>h)
74.  
    cout<<"YES"<<endl;
75.  
    else cout<<"NO"<<endl;
76.  
    }
77.  
    return 0 ;
78.  
    }

1002 最优装载

描述

有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。 

编程任务： 对于给定的n个集装箱和轮船的载重量C，编程计算装入最多时的集装箱个数。

输入

输入由多组测试数据组成。每组测试数据输入的第1行中有2个正整数n和C。正整数n是集装箱个数；正整数C是轮船的载重量。接下来的一行中有n个整数，分别表示n个集装箱的重量，它们之间用空格分隔。其中1<=n<=2000，所有正整数不超过231-1

输出

对应每组输入，输出的每行是计算出的装入最多时的集装箱个数。

样例输入

4 5
3 5 2 1

样例输出

2

输入条件是所有正整数不能超过2的31次方-1，数据定义用longlong比较保险。从小到大排序后判断下一个准备搬的货物是否超过最大重量即可。如果超过就不用继续往下看了。这题还是比较简单的。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define maxn 2001
4.  
   int main()
5.  
   {
6.  
   int i,j,k;
7.  
   long long int n,a[maxn],s,sum,c;
8.  
   while(scanf("%lld%lld",&n,&c)!=EOF){
9.  
    
10.  
     
11.  
    for(i=0;i<n;i )
12.  
    {
13.  
     
14.  
    scanf("%lld",&a[i]);
15.  
    }
16.  
    sort(a,a n);
17.  
    for(i=0;i<n;i )
18.  
    {
19.  
     
20.  
    sum =a[i];
21.  
    if(sum<=c)
22.  
    s=i 1;
23.  
     
24.  
    }
25.  
    printf("%lld\n",s);
26.  
    s=0;
27.  
    sum=0;
28.  
    memset(a,0,sizeof(a));
29.  
    }
30.  
    return 0;
31.  
     
32.  
    }

1003 校报面试

描述

暑假结束了,10届的莘莘学子也迎来了他们的大学生活。

刚刚步入大学的新生们，面对着与高中迥然相异的大学，许多选择也都摆在了他们面前，因此双眼不免应接不暇。

作为大学，众多的社团是大学生活之所以精彩纷呈的一个重要元素，它们不仅能丰富同学们的校园生活，还能提高同学们的综合能力。而想进入这些社团，你必须经过多方面的角逐，它包括一轮轮的面试和笔试。

要进入校报，必须经过面试、笔试、再面试三轮流程。由于有两轮面试，所以面试的时间必须规划好，尽量减少每个人的平均等待时间，以便提高效率。

那么，问题就来了。对于面试者来说，如何用最有效的时间充分地、全面地展示自己，成了他们必须要考虑的一个问题；而对于校报的工作人员来说，如何定位好每轮面试的时间及每位面试者的时间，他们也要有个初步的策划。所以，根据每个人表达需要的时间，为面试的顺序做出安排，使得每个面试者平均等待时间最少。

作为一位acmer，请你帮助校报的工作人员安排一下校报的面试顺序。

输入

输入有多组测试数据

每组数据包含两行

第一行为N（N<=17000）

第二行分别表示第1个人到第N个人每人的表达时间T1，T2，…，Tn（Ti不超过100，面试时间可以为0），每个数据之间有1个空格。

输出

这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

样例输入

5
10 20 30 40 50

样例输出

40.00

这题用c写，double类型的数组直接用c 里自带的sort好像用不了。等我再去研究研究。注意数组的长度。这题就是接水问题的初级版本。

1.  
   #include<stdio.h>
2.  
   #include<string.h>
3.  
   #define maxn 17001
4.  
   void sort(int n,double a[])
5.  
   {
6.  
    
7.  
   int i,j;
8.  
   double t;
9.  
   for(i=1;i<n;i )
10.  
    {
11.  
    for(j=0;j<n-1;j )
12.  
    {
13.  
    if(a[j]>a[j 1])
14.  
    {
15.  
    t=a[j];
16.  
    a[j]=a[j 1];
17.  
    a[j 1]=t;
18.  
     
19.  
    }
20.  
    }
21.  
    }
22.  
    }
23.  
    int main()
24.  
    {
25.  
    int i,j,k;
26.  
    double sum=0,a[maxn],n,t;
27.  
    while(scanf("%lf",&n)!=EOF){
28.  
     
29.  
     
30.  
    for(i=0;i<n;i )
31.  
    {
32.  
    scanf("%lf",&a[i]);
33.  
    }
34.  
    sort(n,a);
35.  
    for(i=0;i<n-1;i ){
36.  
    for(j=0;j<n-i-1;j )
37.  
    {
38.  
    sum =a[i];
39.  
    }
40.  
    }
41.  
    t=sum/n;
42.  
    printf("%.2f\n",t);
43.  
    memset(a,0,sizeof(a));
44.  
    sum=0;
45.  
     
46.  
     
47.  
    }
48.  
    return 0;
49.  
     
50.  
     
51.  
    }

那么接下来看一道接水问题

1004 排队接水

描述

有n个人在一个水龙头（领头）（领头）前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。

输入

共两行，第一行为n(1≤n≤1000)第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。

输出

有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

样例输入

10                            
56 12 1 99 1000 234 33 55 99 812

样例输出

3 2 7 8 1 4 9 6 10 5
291.90
和上面那题联系起来看。总体来说比较基础，不多赘述。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define maxn 1001
4.  
   int main()
5.  
   {
6.  
   int n,a[maxn],i,j,k,t,q=0,c[maxn];
7.  
   double sum=0;
8.  
   memset(c,0,sizeof(c));
9.  
   scanf("%d",&n);
10.  
    for(i=0;i<n;i )
11.  
    {
12.  
    c[i]=i 1;
13.  
    scanf("%d",&a[i]);
14.  
     
15.  
    }
16.  
    sort(a,a n);
17.  
    sort(c,c n);
18.  
    for(i=0;i<n;i )
19.  
    {
20.  
    if(i==n-1)
21.  
    printf("%d",c[i]);
22.  
    else
23.  
    printf("%d ",c[i]);
24.  
     
25.  
    }
26.  
    printf("\n");
27.  
    for(i=0;i<n;i )
28.  
    {
29.  
    sum =a[i]*(n-i-1);
30.  
     
31.  
    }
32.  
    printf("%.2f",sum/n);
33.  
    return 0;
34.  
     
35.  
     
36.  
    }

1005 MS and the Food Store Ft. Food（2022绍兴市大学生计算机能力测试第一题）

描述

MS is a very NB teammate of Legendary Grandmaster DiDiDi. There are endless stories about how they won the champion on various Grand Prix. One day after they get the championship in GP of Zhijiang, MS goes to Zhijiang food street to find something to eat tonight. After visiting every food shop in the street, he finds out that there are n kinds of food in the food street, and the price of the i-th kind of food is pi. However, as a master of constructive problems, MS wants to choose as many kinds of food as possible from these n kinds of food, such that the sum of the prices of any two different kinds of food is less than or equal to x. MS has already known the answer to the problem, so he wants to challenge you.

输入

The first line contains two positive integers n, x, where 1 ≤ n ≤ 105 and 1 ≤ x ≤ 109. The second line contains n integers p1, p2, · · · , pn, where 1 ≤ pi ≤ 109 for all 1 ≤ i ≤ n.

输出

Output an integer representing the maximum kinds of food that can be chosen.

样例输入

6 6
1 1 2 3 4 5

样例输出

4

提示

Sample Input 2

2 2

3 3

Sample Output 2

1

For the first sample, we could at most choose 4 kinds of food. For example, {1, 1, 2, 3}, {1, 1, 2, 4} is valid. But we cannot choose {1, 1, 2, 3, 4} since 3 4 > 6. For the second sample, since we cannot choose two different kinds of food from one kind of food, although 3 > 2, it is ok to choose {3}

背包问题。意思就是说，第一行第一个数字是一共有多少种食物，第二个数字是一共有多少钱。那么从下面的 食物中挑选几种组合成一个数组，在这个数组里，你任意选两个价格加起来都不会超过你有的钱。如果说供你挑选的食物里面，最便宜的你也买不起，但你也依然可以挑选一个。

那么就是看数组里面两个最大的加起来是否超过就可以了呗。先排序之后再遍历，如果说，这里的b是用来储存两个食物价格之和，我这样写可以让两个数组共用一个循环，可以提高效率。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define maxn 100001
4.  
   int main()
5.  
   {
6.  
   long long int n,x,a[maxn],b[maxn],i,j,k=0;
7.  
   scanf("%lld%lld",&n,&x);
8.  
   for(i=0;i<n;i )
9.  
   scanf("%lld",&a[i]);
10.  
    sort(a,a n);
11.  
    if(a[0]>=x)
12.  
    k=1;
13.  
    else{
14.  
    for(i=0;i<n-1;i )
15.  
    {
16.  
    b[i]=a[i] a[i 1];
17.  
    if(b[i]<=x)
18.  
    {
19.  
    k=i 2;
20.  
     
21.  
    }
22.  
     
23.  
    }
24.  
    }
25.  
    printf("%lld",k);
26.  
    return 0;
27.  
    }

接下来看两道区间问题

1006 区间问题

描述

有n项工作，每项工作分别在 si时间开始，ti时间结束。对于每项工作你选择参与与否，如果选择 了参与，那么自始至终就必须全程参与。参与工作的时间段不可以重叠(即使是开始的瞬间和结束的瞬间重叠也是不允许的) 。

你的目标是参与尽可能多的参与工作，那么最多能参与多少项工作呢？

输入

输入数据有多组，每组数据：

第一行为正整数n(1<=n<=105)，表示工作的数目；

第二行有n个整数，表示每项工作的起始时间si；

第三行有n个整数，表示每项工作的结束时间ti。

1<=si<=ti<=109

输入以EOF结束。

输出

每组输出一个整数，表示最多能参与的工作数目。

样例输入

5
1 2 4 6 8
3 5 7 9 10
样例输出

3

区间问题一般涉及到结构体。你当然可以用struct，在c 里可以用pair，代表两个元素构成的结构体，比较简洁。这里的sort排序是对结束时间的排序，cmp让排序做到了结束的升序排序（结束时间从早到晚排序），选择肯定是要选结束时间最早的那个，才能做到选的最多。在一个时间段结束后，当然要选择与上一个时间段没有重合的时间段，其中的solve函数就是用来干这个的。这里的cmp函数内就是根据second的值进行升序排序，专门为sort服务的。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define maxn 100001
4.  
   int n,i;
5.  
   pair<int,int> p[maxn];
6.  
   bool cmp(pair<int,int> a,pair<int,int> b)
7.  
   {
8.  
   return a.second<b.second;
9.  
   }
10.  
     
11.  
    int solve()
12.  
    {
13.  
    int t=0,count=0,i;
14.  
    for(i=0;i<n;i )
15.  
    {
16.  
    if(t<p[i].first)
17.  
    {
18.  
    count ;
19.  
    t=p[i].second;
20.  
    }
21.  
    }
22.  
    return count;
23.  
    }
24.  
     
25.  
    int main()
26.  
    {
27.  
    while(cin>>n){
28.  
    for(i=0;i<n;i )
29.  
    {
30.  
    cin>>p[i].first;
31.  
    }
32.  
    for(i=0;i<n;i )
33.  
    {
34.  
    cin>>p[i].second;
35.  
    }
36.  
    sort(p,p n,cmp);
37.  
    cout<<solve()<<endl;
38.  
    }
39.  
    }

1007 今年暑假不AC

描述

“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”

确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。
作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6 7、超级女生，以及王小丫的《开心辞典》等等，假设你已经知道了所有你喜欢看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

输入

输入数据包含多个测试实例，每个测试实例的第一行只有一个整数n(n<=100)，表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e (1<=i<=n)，分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不做处理。

输出

对于每个测试实例，输出能完整看到的电视节目的个数，每个测试实例的输出占一行。

样例输入

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

和上面一题基本上是一模一样的，但是要注意的是。上一题的时间起点是1，这一题的时间起点是0，所以在solve函数里面的范围要进行一些调整，调整成小于等于即可。

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   #define maxn 101
4.  
   int n,i;
5.  
   pair<int,int> p[maxn];
6.  
   bool cmp(pair<int,int> a,pair<int,int> b)
7.  
   {
8.  
   return a.second<b.second;
9.  
   }
10.  
     
11.  
    int solve()
12.  
    {
13.  
    int t=0,count=0,i;
14.  
    for(i=0;i<n;i )
15.  
    {
16.  
    if(t<=p[i].first)
17.  
    {
18.  
    count ;
19.  
    t=p[i].second;
20.  
    }
21.  
    }
22.  
    return count;
23.  
    }
24.  
     
25.  
    int main()
26.  
    {
27.  
    while(cin>>n&&n!=0){
28.  
    for(i=0;i<n;i )
29.  
    {
30.  
    cin >> p[i].first >> p[i].second;
31.  
    }
32.  
    sort(p,p n,cmp);
33.  
     
34.  
    cout<<solve()<<endl;
35.  
    }
36.  
    }

欢迎评论区、私信交流！

这篇好文章是转载于：学新通技术网