一道貪心+類背包DP的好題
首先發現一個十分顯然的性質，沒有這個性質整道題目都難以下手：
無論兩隊的順序如何，總是讓吃飯慢的人先排隊
這是一個很顯然的貪心，因為如果讓吃飯慢的排在后面要更多的時間至少沒有這樣優
因此我們先按吃飯時間從大到小sort一下
然后我們發現這是一個類01背包的DP，只不過這里的狀態要么是01，要么是10（即要么在1隊，要么在2隊）
然后這種東西都有一些很神奇的性質，比如說我們用前綴和sum[i]表示前i個人中排隊的總時間，那么
sum[i]-前i個人中去1號窗口的人的打飯時間之和=前i個人中去1號窗口的人的打飯時間之和
然后我們可以想出一個DP，用f[i][j]表示前i個人中，在1號窗口排隊的人共花了j分鐘排隊的最優情況下，最少要多少時間（要和2號窗口的取一個min），包括吃飯的時間
然后就有轉移：
f[i][j]=min(f[i][j],max(f[i-1][j-a[i].t],j+a[i].e))（在1號窗口打飯）
f[i][j]=min(f[i][j],max(f[i-1][j],sum[i]-j+a[i].e)（在2號窗口打飯）
然后我們發現這個可以滾動存儲不過也沒這個必要，但是我還是寫了
CODE
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205;
struct data
{int t,e;
}a[N];
int n,f[2][N*N],sum[N],ans;
inline char tc(void)
{static char fl[100000],*A=fl,*B=fl;return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{x=0; char ch=tc();while (ch<'0'||ch>'9') ch=tc();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline bool comp(data a,data b)
{return a.e>b.e;
}
inline int min(int a,int b)
{return a<b?a:b;
}
inline int max(int a,int b)
{return a>b?a:b;
}
int main()
{//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);register int i,j;for (read(n),i=1;i<=n;++i)read(a[i].t),read(a[i].e);sort(a+1,a+n+1,comp);for (i=1;i<=n;++i)sum[i]=sum[i-1]+a[i].t;memset(f[0],63,sizeof(f[0])); f[0][0]=0;for (i=1;i<=n;++i){int now=i&1,last=now^1;memset(f[now],63,sizeof(f[now])); ans=f[now][0];for (j=sum[i];j>=0;--j){if (j>=a[i].t) f[now][j]=min(f[now][j],max(f[last][j-a[i].t],j+a[i].e));if (sum[i]-j>=a[i].t) f[now][j]=min(f[now][j],max(f[last][j],sum[i]-j+a[i].e));}}for (i=0;i<=sum[n];++i)ans=min(ans,f[n&1][i]);printf("%d",ans);
}
)
