1620: [Usaco2008 Nov]Time Management 时间管理
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 506 Solved: 306
[Submit][Status]
Description
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,问要完成所有工作,最迟要什么时候开始.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: T_i and S_i
Output
* Line 1: The latest time Farmer John can start working or -1 if Farmer John cannot finish all the jobs on time.
Sample Input
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.
Sample Output
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.
HINT
Source
题解:坑爹啊,这次居然CE,吓我一跳——打开一看,代码没复制全TuT。。。突然觉得其实bzoj上面贪心的题才是最令人不敢下手的,看了半天才尝试性的写了个贪心程序,然后碰运气,有时候AC,有时候直接跪。。。书归正传,这个题其实就是先按照deadline时间排个序,然后不断的往前减当前任务消耗的时间,假如出现了减去后小于0的情况,就出-1,还有注意每次减去后到了下一次,然后要和这个新的任务deadline比较小,假如deadline更小的话,则取deadline再减,否则凉拌。。。
type
arr=array[..] of longint;
var
i,j,k,l,m,n:longint;
a,b:arr;
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
procedure sort(l,r:longint);
var
i,j,x,y:longint;
begin
i:=l;j:=r;
x:=a[(l+r) div ];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if I<=j then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i);dec(j);
end;
until I>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
begin
readln(n);
for i:= to n do
readln(b[i],a[i]);
sort(,n);
l:=a[n];
for i:=n downto do
begin
l:=min(l,a[i]);
l:=l-b[i];
if l< then
begin
writeln(-);
halt;
end;
end;
writeln(l);
end.