[BZOJ1664] [Usaco2006 Open]County Fair Events 参加节日庆祝

本文主要是介绍[BZOJ1664] [Usaco2006 Open]County Fair Events 参加节日庆祝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[Usaco2006 Open]County Fair Events 参加节日庆祝

Description

Farmer John has returned to the County Fair so he can attend the special events (concerts, rodeos, cooking shows, etc.). He wants to attend as many of the N (1 <= N <= 10,000) special events as he possibly can. He’s rented a bicycle so he can speed from one event to the next in absolutely no time at all (0 time units to go from one event to the next!). Given a list of the events that FJ might wish to attend, with their start times (1 <= T <= 100,000) and their durations (1 <= L <= 100,000), determine the maximum number of events that FJ can attend. FJ never leaves an event early.

有N个节日每个节日有个开始时间,及持续时间. 牛想尽可能多的参加节日,问最多可以参加多少. 注意牛的转移速度是极快的,不花时间.

Input

• Line 1: A single integer, N.

• Lines 2..N+1: Each line contains two space-separated integers, T and L, that describe an event that FJ might attend.

Output

• Line 1: A single integer that is the maximum number of events FJ can attend.

Sample Input

7

1 6

8 6

14 5

19 2

1 8

18 3

10 6

Sample Output

4

OUTPUT DETAILS:

FJ can do no better than to attend events 1, 2, 3, and 4.

Source

Silver

题解

贪心，按结束时间排序

vara:array[0..10000,1..2]of longint;i,j,k:longint;n,b,ans:longint;
procedure sort(l,r: longint);
var i,j,x,y: longint;
begini:=l; j:=r; x:=a[(l+r) div 2,2];repeatwhile a[i,2]<x do inc(i);while x<a[j,2] do dec(j);if not(i>j) thenbeginy:=a[i,2]; a[i,2]:=a[j,2]; a[j,2]:=y;y:=a[i,1]; a[i,1]:=a[j,1]; a[j,1]:=y;inc(i); dec(j);end;until i>j;if l<j then sort(l,j);if i<r then sort(i,r);
end;beginreadln(n);for i:=1 to n dobeginreadln(a[i,1],b);a[i,2]:=b+a[i,1];end;sort(1,n); ans:=0; b:=0;for i:=1 to n doif b<=a[i,1]then begin inc(ans); b:=a[i,2]; end;writeln(ans);
end.

这篇关于[BZOJ1664] [Usaco2006 Open]County Fair Events 参加节日庆祝的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---