一开始想到贪心,按照吃饭时间长到短进行排序。
正确性显然,可以用微扰进行证明。
之后就是如何DP的事情了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=205;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int f[N][N*N],sum[N];
struct node{int a,b;bool operator <(const node a)const{return b>a.b;}}p[N];
int main()
{
    int n;qr(n);
    for(int i=1;i<=n;i++)qr(p[i].a),qr(p[i].b);
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+p[i].a;
    memset(f,0x3f,sizeof f);f[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=sum[i];j++)
        {
            if(j>=p[i].a)f[i][j]=min(f[i][j],max(f[i-1][j-p[i].a],j+p[i].b));
            f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+p[i].b));
        }
    int ans=0x3f3f3f3f;
    for(int i=0;i<=sum[n];i++)
        ans=min(ans,f[n][i]);
    qw(ans);puts("");
    return 0;
}