看电影

题目类型

贪心

题目描述

马上要期末考试了，本周六浙江财经学院电影院将是本学期最后一次放映电影。考虑到很多学生要看电影，为了满足这些学生的要求，电影院决定从凌晨0点开始放映，一直放映到午夜24点整(^-^，是不是很疯狂？！)。电影院有很多个放映厅，分别放映不同的电影，以供学生选择。电影院提前通知了每部电影的放映时间和所在放映厅。但是，学校要求周六那天电影院在指定的时间段某放映厅要放映一部政治宣传电影，而且要求每个学生党员都要观看。

小王很喜欢看电影。在电影院贴出放映电影名称和时间的那天他就去看通知了。幸运的是，这些电影小王都喜欢看，不幸的是有些电影时间上有冲突，更不幸的是，他是党员，必须在指定的时间观看指定的政治片。请帮帮小王安排时间，使得他能看到最多的电影。

输入

输入文件中包含多个测试数据。每个测试数据的第1行为一个正整数N(1<=N<=20)，表示电影院周六那天放映的电影数(不包括政治片)；然后是2行，第2行为N部电影各自的开始时间s，第3行为N部电影各自的结束时间t，0<=s<t<=24，s和t均为整数；如果这N部电影中某些电影时间有冲突，则表示这些电影是在不同放映厅放映的；第4行为两个整数m和n，表示学校指定政治片的开始时间和结束时间，0<=m<n<=24。N = 0表示输入结束。

输出

对输入文件中的每个测试数据，输出小王最多能观看到的电影数(不包括必须看的政治片，因为这本来不是小王所想看的)。

思路

先将与政治电影冲突的电影删去，把剩下的有可能看上的电影存储到新的数组，然后进行贪心，求出最多电影数
样例输入

8
0 1 4 7 9 10 13 12
7 4 9 13 15 13 19 15
5 10
0

样例输出

3

上代码

#include<bits/stdc++.h>
using namespace std;

struct watching{
    int s;//开始时间 
    int e;//结束时间 
}a[100];

bool cmp(watching x,watching y)
{
    return x.e<y.e;//23行调用 
}
//这一题以电影的结束时间做排序，计算可以看的最大电影数 

int main(){
    int t,i,m,n; 
    watching b[100];//用于存储删去与政治电影冲突的电影 

    while(cin>>t)//输入t 
    {
        memset(b,0,sizeof(b));//每一组数组将b数组初始化为0 
        if(t==0)break;//数据结束标志 

        for(i=0;i<t;i++)
            cin>>a[i].s;
        for(i=0;i<t;i++)
            cin>>a[i].e;
        cin>>m>>n;//开始与结束的时间 

        sort(a,a+t,cmp);//以结束时间为标准将a数组从小到大排 

        int j=0,flag=0;
        for(i=0;i<t;i++)
        {
            if(a[i].s>=n||a[i].e<=m){//判断是否符合不与政治电影冲突 
                b[j].s=a[i].s;
                b[j].e=a[i].e;//存储数据 
                j++;
                flag=1;//标记                
            }
        }

        if(flag==0){//如果全部电影都与政治电影冲突，输出0 
            cout<<0<<endl;
        }
        else {//反之，进入计算 
            int last=b[0].e;//新的第一个电影的结束时间 
            int ans=1;//记录答案 
            for(i=0;i<j;i++)
            {
                if(b[i].s>=last){//下一个电影的开始时间大于上一个电影的结束时间 
                    ans++;//答案++ 
                    last=b[i].e;//接入新的电影结束时间 
                }
            }
            cout<<ans<<endl;//输出答案，注意不包括政治电影
        }
    } 
    return 0;
}