首页 > 代码库 > USACO 2014 JAN 滑雪录像
USACO 2014 JAN 滑雪录像
2. 滑雪录像{silver题3}
【问题描述】
冬奥会的电视时刻表包含N (1 <= N <= 150)个节目，每个节目都有开始和结束时间。农民约翰有两台录像机，请计算他最多可以录制多少个节目。
【文件输入】
第一行，一个整数N。
接下来N行每行两个整数，表示一个节目的开始和结束时间，范围为0..1,000,000,000。
【文件输出】
一个整数，表示最多可以录制的节目数量。
【输入样例】
6
0 3
6 7
3 10
1 5
2 8
1 9
【输出样例】
4
【样例说明】
第1台录制节目1和3，第2台录制节目2和4。
首先感谢 宝宝的思路分享~
思路：
贪心，因为是两个相机，所以如果用动归的话，就会出现重复使用，方大神动归只有70，因为特判比较复杂，本渣就放弃了。
开始写了暴搜，可是同样因为重叠的原因，只有10分，所以还是贪心。
贪心的思路就是，首先按照结束时间b[i]进行排序，（为什么不用开始时间呢，因为如果按照开始时间排序，会出现开始时间很小，但是时间段很长的情况，这样的话，就会影响最优）。 然后设两个变量来记录两个相机当前节目的结束时间，然后从1到n个节目进行比较，可加入就加入。
PS：当两个相机都可以加入的时候，应选取结束时间靠后的相机加入。原因：因为是按照结束时间排序，有可能会出现后来的节目开始时间比此节目靠前，此时可将其加入到之前结束时间靠前的相机中。
举例说明：
|------| 结尾时间4
|----------| 结尾时间6
比如上面为两个相机已加入的时间段， 现在再加入一条开始时间为9的，则应加入到第二个，因为如果下一个节目开始时间为5，则又可以加入到第一个，若将9的加入到第一个， 则5的就无法加入，就无法最优。
program recording;var i,j,k,n,m,x,y:longint;a,b:array[0..100001] of longint;procedure data1;var i,j:longint; begin assign(input,‘recording.in‘); assign(output,‘recording.out‘); reset(input); rewrite(output); end;procedure data2; begin close(input); close(output); end; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=b[(l+r) div 2]; repeat while b[i] inc(i); while x dec(j); if not(i>j) then begin y:=b[i]; b[i]:=b[j]; b[j]:=y; y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j; if l sort(l,j); if i sort(i,r); end;procedure datain;var i,j,x,y,ans:longint; begin readln(n); for i:=1 to n do readln(a[i],b[i]); sort(1,n); x:=0;y:=0;ans:=0; for i:=1 to n do begin if (a[i]>=x) and (a[i]>=y) then if x>y then begin inc(ans);x:=b[i]; continue; end else begin inc(ans);y:=b[i]; continue; end; if a[i]>=x then begin inc(ans);x:=b[i]; end; if a[i]>=y then begin inc(ans);y:=b[i]; end; end; writeln(ans); end;begin data1; datain; data2;end.
USACO 2014 JAN 滑雪录像
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。