上海计算机学会2022年10月月赛C++乙组T1录制节目
发布时间
阅读量：
阅读量
录制节目
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
电视里将要播放 n 个节目，第 i 个节目从时刻 si 开始，到 ti 结束，没有回放。小爱有两台录像机，每台录像机在工作的时候只能录一个节目，小爱最多可以录下多少完整的节目呢？
如果某节目的结束时间等于另一个节目的开始时间，那么这两个节目是可以用一台录像机的。
输入格式
第一行：单个整数 n
第二行到第 n+1行：第 i+1 行有两个整数 si 和 ti
输出格式
单个整数：表示最大可以录制的节目数量。
数据范围
- 对于 30% 的数据，n≤500
- 对于 60% 的数据，n≤2000
- 对于 100% 的数据，1≤n≤200,000
- 0≤si,ti≤1,000,000,000
样例数据
输入:
5
1 5
2 6
8 10
3 9
5 10
输出:
4
解析：
贪心算法。
详见代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int st,ed;//开始时间，结束时间
}a[200010];
bool cmp(node a,node b){//按结束时间从小到大排序
return a.ed<b.ed;
}
int main(){
int n,ans=0;
int time1=0,time2=0;//录像机1和录像机2最后一个节目结束的时间
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d",&a[i].st,&a[i].ed);
}
sort(a+1,a+n+1,cmp);//排序
for(int i=1;i<=n;i++){
if(time1<time2){//始终让录像机1结束时间晚于录像机2结束时间
swap(time1,time2);
}
if(a[i].st>=time1){//尽量使用结束时间晚的录像机1录像
time1=a[i].ed;
ans++;
}else if(a[i].st>=time2){//1不行，录像机2再录
time2=a[i].ed;
ans++;
}
}
printf("%d",ans);
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~