Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 506 Solved: 306
Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish (like milking the cows, cleaning the barn, mending the fences, and so on). To manage his time effectively, he has created a list of the jobs that must be finished. Job i requires a certain amount of time T_i (1 <= T_i <= 1,000) to complete and furthermore must be finished by time S_i (1 <= S_i <= 1,000,000). Farmer John starts his day at time t=0 and can only work on one job at a time until it is finished. Even a maturing businessman likes to sleep late; help Farmer John determine the latest he can start working and still finish all the jobs on time.
N个工作,每个工作其所需时间,及完成的Deadline,问要完成所有工作,最迟要什么时候开始.
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and S_i
* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.
4 3 5 8 14 5 20 1 16 INPUT DETAILS: Farmer John has 4 jobs to do, which take 3, 8, 5, and 1 units of time, respectively, and must be completed by time 5, 14, 20, and 16, respectively.
2 OUTPUT DETAILS: Farmer John must start the first job at time 2. Then he can do the second, fourth, and third jobs in that order to finish on time.
题解:坑爹啊,这次居然CE,吓我一跳——打开一看,代码没复制全TuT。。。突然觉得其实bzoj上面贪心的题才是最令人不敢下手的,看了半天才尝试性的写了个贪心程序,然后碰运气,有时候AC,有时候直接跪。。。书归正传,这个题其实就是先按照deadline时间排个序,然后不断的往前减当前任务消耗的时间,假如出现了减去后小于0的情况,就出-1,还有注意每次减去后到了下一次,然后要和这个新的任务deadline比较小,假如deadline更小的话,则取deadline再减,否则凉拌。。。
1 type
2 arr=array[0..2000] of longint;
3 var
4 i,j,k,l,m,n:longint;
5 a,b:arr;
6 procedure swap(var x,y:longint);
7 var z:longint;
8 begin
9 z:=x;x:=y;y:=z;
10 end;
11 function min(x,y:longint):longint;
12 begin
13 if x<y then min:=x else min:=y;
14 end;
15 procedure sort(l,r:longint);
16 var
17 i,j,x,y:longint;
18 begin
19 i:=l;j:=r;
20 x:=a[(l+r) div 2];
21 repeat
22 while a[i]<x do inc(i);
23 while a[j]>x do dec(j);
24 if I<=j then
25 begin
26 swap(a[i],a[j]);
27 swap(b[i],b[j]);
28 inc(i);dec(j);
29 end;
30 until I>j;
31 if l<j then sort(l,j);
32 if i<r then sort(i,r);
33 end;
34 begin
35 readln(n);
36 for i:=1 to n do
37 readln(b[i],a[i]);
38 sort(1,n);
39 l:=a[n];
40 for i:=n downto 1 do
41 begin
42 l:=min(l,a[i]);
43 l:=l-b[i];
44 if l<0 then
45 begin
46 writeln(-1);
47 halt;
48 end;
49 end;
50 writeln(l);
51 end.
52