首页 > 代码库 > USACO 2014 JAN 滑雪录像{silver题3}

USACO 2014 JAN 滑雪录像{silver题3}

2024-07-31 05:09:53   220人阅读

滑雪录像{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。

 

 

思路：一开始觉得用两次DP，第一次DP得出最优解，之后将最优解删去，再DP，最后得出的就是答案，但是本题由于两个录像可能会有覆盖，这样两次DP就需要有特判，然后特判很烦，也就没打，只有70分。后来得知本题原来可以贪心，我也是醉了、、、先将结束时间进行排序，然后记录两台录像机当前最后一个的结束时间，如果一个录像只能由一台相机录，那就给它录，如果两台录像机都可以录此录像，那么就选两台录像机中结束时间晚的那个来录它（至于为什么，也不用说了，自己想）。接下来上代码

 1 var 2 s,t:array[0..150]of longint; 3 i,n,t1,t2,ans:longint; 4  5 procedure openit; 6  begin 7   assign(input,‘recording.in‘);assign(output,‘recording.out‘); 8   reset(input);rewrite(output); 9  end;10 11 procedure closeit;12  begin13   close(input);close(output);14  end;15 16 procedure qsort(l,r:longint);17  var i,j,m,temp:longint;18   begin19    i:=l;j:=r;m:=t[(l+r) div 2];20    repeat21     while t[i]<m do inc(i);22     while t[j]>m do dec(j);23     if not (i>j) then24      begin25       temp:=s[i];s[i]:=s[j];s[j]:=temp;26       temp:=t[i];t[i]:=t[j];t[j]:=temp;27       inc(i);dec(j);28      end;29    until i>j;30    if l<j then qsort(l,j);31    if i<r then qsort(i,r);32   end;33 34 35 begin36  openit;37  readln(n);38  for i:=1 to n do readln(s[i],t[i]);39  qsort(1,n);      //快排结束时间40  t1:=0;t2:=0;ans:=0;41  for i:=1 to n do42   begin43    if (s[i]>=t1) and (s[i]>=t2) then44     begin45      inc(ans);46      if t1>t2 then t1:=t[i]47               else t2:=t[i];48      continue;49     end;50    if s[i]>=t1 then begin inc(ans);t1:=t[i]; end;51    if s[i]>=t2 then begin inc(ans);t2:=t[i]; end;52   end;53  writeln(ans);54  closeit;55 end.

 

USACO 2014 JAN 滑雪录像{silver题3}


联系
我们