首页 > 代码库 > XidianOJ 1091 看Dota视频的V8
XidianOJ 1091 看Dota视频的V8
题目描述
V8作为一个Dota lover,因为在某次和小伙伴开黑对战“简单的电脑”时被电脑血虐,V8痛定思痛之后,发现是时候学一发Dota教学视频了。现在,V8在网上找到了n个Dota直播教学视频,并且知道每个视频的开始时间和结束时间,现在V8想知道他作出合理安排之后他最多看多少个完整的Dota视频。
输入
多组数据,n==0时文件结束。每组数据第一行一个数字n(1<=n<=10^3),接下来n行每行两个数字li,ri,表示视频的开始时间和结束时间(0<=li<=ri<=2*10^4)。
输出
每组数据一行输出,表示V8最多能看到的完整教学视频的数量。
--正文
贪心的线段覆盖问题,换了个皮
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct VideoNode { int begin; int end; }; struct VideoNode video[1001]; int cmp(struct VideoNode v1,struct VideoNode v2){ return (v1.end < v2.end); } int main(){ int n; while (scanf("%d",&n) != EOF){ if (n == 0) break; int i; for (i=0;i<n;i++){ int begin,end; scanf("%d %d",&begin,&end); video[i].begin = begin; video[i].end = end; } sort(video,video+n,cmp); int total = 0,time = -1; for (i=0;i<n;i++){ if (video[i].begin >= time){ time = video[i].end; total ++; } } printf("%d\n",total); } return 0; }
XidianOJ 1091 看Dota视频的V8
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。