题解
二分+贪心
每次优先完成期限最短且时间最短的任务。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
35
36
37
38
39
40
41
42
using namespace std;
typedef long long ll;
int n,t[1005],s[1005],mini=INF;
pair<int,int> P[1005];
bool judge(int M){
for(int i=0;i<n;i++){
if(M+P[i].second<=P[i].first)
M+=P[i].second;
else return 0;
}
return 1;
}
void init(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&t[i],&s[i]),
P[i].first=s[i],P[i].second=t[i],
mini=min(mini,s[i]);
sort(P,P+n);
}
void solve(){
int L=0,R=mini,M;
while(R-L){
M=(R+L+1)/2;
if(judge(M))
L=M;
else R=M-1;
}
if(!judge(0))L=-1;
printf("%d\n",L);
}
int main(){
init();
solve();
return 0;
}