USACO08NOV时间管理TimeManagement

发表于

洛谷2920 BZOJ1630

  • 题意
    有$N$个工作要做，第$i$个工作要$T_i$完成，且必须在$S_i$之前完成。请输出最晚开始工作的时间，无解输出$-1$.
  • Solution
    • 贪心性质显而易见，从后往前将离终点最近的工作做了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std ;
const int maxn = 1005 ;
void Read ( int &x, char c = getchar() ) {
	for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
	for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
struct node {
	int tim, end ;
	friend bool operator < ( node a, node b ) {
		return a.end < b.end ;
	}
} s[maxn] ;
int n, m ;
int main() {
#ifndef ONLINE_JUDGE
	freopen ( "LG2920.in", "r", stdin ) ;
	freopen ( "LG2920.out", "w", stdout ) ;
#endif
	int i ;
	Read(n) ;
	for ( i = 1 ; i <= n ; i ++ ) {
		Read(s[i].tim) ; Read(s[i].end) ;
	}
	sort ( s+1, s+n+1 ) ;
	int now = s[n].end ;
	for ( i = n ; i ; i -- ) {
		now = min(now, s[i].end) ;
		now -= s[i].tim ;	
	}
	if ( now < 0 ) now = -1 ;	
	printf ( "%d\n", now ) ;	
	return 0 ;
}