HDU 3697 Selecting courses（贪心）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3697

2
1 10
4 5
0

2

题意：

有n门课程(n<=300),每门课程有个选课的时间段s,e,只能在s之后，在e之前选择该门课程。每位同学可以选择任意一个开始时间，然后每5分钟有一次选课机会，问每位同学最多可以选多少门课。

PS:

贪心，枚举开始的5个人时间！每次选择课程结束时间最早的！

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 317;
struct sub
{
    int s;
    int e;
};
bool cmp(sub x, sub y)
{
    if(x.e == y.e)
    {
        return x.s < y.s;
    }
    return x.e < y.e;
}
int main()
{
    sub a[maxn];
    int t;
    int n;
    int vis[maxn];
    while(scanf("%d",&n) && n)
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d",&a[i].s,&a[i].e);
        }
        sort(a,a+n,cmp);
        int ans = 0, cont = 0;
        for(int i = 0; i < 5; i++)
        {
            memset(vis,0,sizeof(vis));
            cont = 0;
            for(int j = i; j < a[n-1].e; j += 5)
            {
                for(int k = 0; k < n; k++)
                {
                    //printf("%d %d %d\n",j,a[k].s,a[k].e);
                    if(!vis[k] && j>=a[k].s && j<a[k].e)
                    {
                        cont++;
                        vis[k] = 1;
                        break;
                    }
                }
            }
            if(ans < cont)
            {
                ans = cont;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU 3697 Selecting courses（贪心）

原文：http://blog.csdn.net/u012860063/article/details/41143545