上次讲了进阶sort与重载运算符，上题：

题目描述：
输入n个学生的姓名、学号、成绩，查询其中m名同学的成绩。

输入描述：
第一行一个正整数n，表示有n名同学。
接下来n行，每行为一名同学的姓名、学号、成绩。
接下来一行一个正整数m，表示查询其中m名同学的成绩。
接下来一行，有m个正整数，中间用空格隔开，对于第i个数mi，表示排名第mi的同学的成绩。成绩越高的同学排名越靠前，如果两名同学成绩相同，学号小的同学成绩靠前。

输出描述：
m行，每行输出排名第mi的同学的姓名、学号、成绩，中间用空格隔开。

输入样例：
3
Galon 20161103 100
Bruce 20161105 10
Dijkstra 20161102 30
1
2

输出样例：
Dijkstra 20161102 30

其他说明：
名字不超过10个字符，0<m<n<10000，所有数据均在int范围内。
RFdragon的英文名叫Galon

 　　今天来讲一下贪心。所谓贪心，就是怎么贪怎么来，所有场攻全走脸（hearthstone），哪种棋子多买哪种（autochess），一套卡组带八张传奇(COR)……大家听完我的描述之后，觉得贪心实在是太废物了，我们还是不学了吧。但是等一下，贪心虽然废物，但有些题确实要用贪心的思想来做。比如下面的一道题：

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
题目描述：
学生节到了，RFdragon要在学校的会议室举办n个活动，但由于时间有冲突，不得不取消其中一部分活动。给出n各个活动的起始和终止时间，求出最多能排多少个活动。由于RFdragon十分勤劳能干，活动的准备时间几乎为0，也就是说一个活动结束后可以立即举办下一个活动。

输入描述：
第一行一个正整数n，表示有n个打算举办的活动。
接下来n行，每行两个正整数，分别表示一个活动的起始和终止时间。

输出描述：
一行一个正整数，表示最多能举办的活动数。

输入样例：
3
1 4
2 3
3 4

输出样例：
2

其他说明：
n<10000，所有数据均在int范围内。

　　这时，我们就可以来贪一贪。c++中的贪心指的是：在解决问题是，做出当前最好的选择，也就是说，不考虑整体，而只考虑局部最优解。看看对贪心的描述，好像根本得不到这道题的最优解。其实，这道题是一道经典的贪心题，完全能用贪心做出来，关键看你怎么贪。我们要贪的是结束时间，也就是每次找出结束时间最早的活动，优先选择它。代码如下：

#include<algorithm>
#include<cstdio>
using namespace std;
struct acti
{
    int start,end;
    bool operator<(const acti x)const
    {
        return end<x.end;
    }
}a[10000];
int n,cur,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d",&a[i].start,&a[i].end);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        if(a[i].start>=cur)
        {
            ans++;
            cur=a[i].end;
        }
    printf("%d",ans);
    return 0;
}

　　这就是贪心算法的精髓——选择一个不会影响结果的标准对所有可能选项进行排序，优先选择排在前面的选项。

　　这就是贪心的用法，你学会了吗？

//答案代码
#include<algorithm>
#include<cstdio>
using namespace std;
struct student
{
    char name[10];
    int num,score;
    bool operator<(const student x)const
    {
        if(score>x.score)
            return 1;
        if(score<x.score)
            return 0;
        return num>x.num;
    }
}stu[10000];
int n,m,a[10000];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%s %d %d",&stu[i].name,&stu[i].num,&stu[i].score);
    sort(a+1,a+1+n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    for(int i=i;i<=m;i++)
        printf("%s %d %d\n",stu[a[i]].name,stu[a[i]].num,stu[a[i]].score);
    return 0;
}

Created by RFdragon

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄