容易想到贪心：吃饭慢的先打饭节约时间， 所以先将人按吃饭时间从大到小排序。
是可以证明无论怎么交换，都没有这样选优的。在这里由于我太菜了，就不写证明了
我们设dp[i][j]表示前i个人 在1号窗口打饭总时间为j 最早吃饭完的时间 那也就顺便可以推出在二号窗口的打饭总时间了
影响到当前dp[i][j]的：1~i-1最早吃完饭的时间和第i个人打完饭+吃饭的时间 很显然 如果前者比后者都还要晚 那当前这个人根本不影响总时间的花费 所以取个max（在1号窗口）
2号窗口同理
#include<bits/stdc++.h> #define N 205 #define INF 0x3f3f3f3f using namespace std; int n,sum[N],dp[N][N*N]; struct Data { int a,b; }x[N]; inline bool cmp(const Data &x,const Data &y) { return x.b>y.b; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>x[i].a>>x[i].b; sort(x+1,x+n+1,cmp); //先选吃的久的 for(int i=1;i<=n;i++) sum[i]=sum[i-1]+x[i].a; memset(dp,63,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=sum[i];j++) //枚举一号窗口用时 { if(j>=x[i].a) dp[i][j]=min(dp[i][j],max(dp[i-1][j-x[i].a],j+x[i].b)); dp[i][j]=min(dp[i][j],max(dp[i-1][j],sum[i]-j+x[i].b)); //二号窗口 } } int ans=INF; for(int i=0;i<=sum[n];i++) ans=min(ans,dp[n][i]); cout<<ans; return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9840483.html
