书海扬帆的博客

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,ans;
struct lunch {
int a,b;
//a 打饭时间
//b 吃饭时间
}t[222];
bool cmp(lunch p,lunch q)
{
return p.b>q.b;
}
int dp[400040],s[1010],sum;
//表示
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&t[i].a,&t[i].b);
sort(t+1,t+n+1,cmp);
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++) s[i]=s[i-1]+t[i].a;
for(int i=1;i<=n;i++) {
for(int j=sum;j>=0;j--) {
dp[j+t[i].a]=min(dp[j+t[i].a],max(dp[j],t[i].b+j+t[i].a));
dp[j]=max(dp[j],t[i].b+s[i]-j);
}
sum+=t[i].a;
}
ans=2147483647;
for(int i=1;i<=sum;i++) ans=min(ans,dp[i]);
printf("%d\n",ans);
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k