【ZJOI2005】午餐

再次自己想出来，感动 原题： 上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。 THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。 现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。 假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。 现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。 所有输入数据均为不超过200的正整数。 这个题意看上去就有让人想贪心的欲望啊 那不妨先来玩一下，不难发现，b值大的一定要排在前面打饭 在说明贪心为什么是对的之前，我们需要注意到一条很重要的特殊性： 在做高考物理题的时候，一个很重要的思路是注意什么是守恒的 首先可以大胆猜测，如果上面的贪心是对的话，这题的决策很可能只需要考虑第i个人应该排在哪一队 现在研究在一个队伍里的人有什么性质 可以发现道题里也有一个不变量，就是对于队伍里的前i个人，不管他们排队的顺序如何，a[i]的前缀和s[i]是不会变的，第i个人会在s[i]+b[i]时刻吃完，这前i个人的吃饭时间是max{s[j]+b[j]} 现在可以回到贪心的问题上了，假设对于两个相邻的人i和i+1，如果a[i]==a[i+1]，那么显然让b[i]>b[i+1]好 由上面的性质可以看到s[i]是守恒的，那么让第i个人的b[i]是前i个人里最小的当然就是坠吼的啦 明确了这个贪心策略之后，现在需要考虑的是按b排序后，第i个人要放在哪一队 开始设计状态，首先阶段基本确定是以每一个人为阶段，状态的话，我一开始想的是f[i][j][k]表示第i个人，一队a的和是j，二队a的和是k，但是s[i]最高可能是40000，这个方案不可行 这里再次使用上面的性质（特殊性在OI题里是多么重要呀~ 在每一队里a[i]的前缀和是守恒的，两队的前i个人的a[i]加起来也是守恒的，所以实际上只需要记录j就可以了，k可以计算得到 （注意这里s[i]不再是指每一队的前缀和，而是所有人里的前缀和 状态转移方程就很容易写出来了： $$ f[i][j]=min\{max\{f[i-1][j-a[i]],j+b[i]\},max\{f[i-1][j],s[i]-j+b[i]\}\} $$ 其中f[i-1][j-a[i]]表示上一个状态的最优值，j+b[i]表示第i个人在这个状态下的值，两个值比较后送到当前状态更新，第二个max同理 代码非常好实现，没有什么坑，又1A了好开心啊~ 代码： ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int rd(){int z=0,mk=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} return z*mk; } struct nds{int x,y;}a[210]; int n; int s[210]; int f[210][41000]; //f[i][j]=min{max{f[i-1][j-a[i]],j+b[i]},max{f[i-1][j],s[i]-j+b[i]}} bool cmp(nds x,nds y){ return x.y==y.y ? x.x>y.x : x.y>y.y;} int main(){freopen("ddd.in","r",stdin); //freopen("ddd.out","w",stdout); memset(f,10,sizeof(f)); cin>>n; //for(int i=1;i<=n;++i) a[i].x=rd(),a[i].y=rd(),s[i]=s[i-1]+a[i].x;//注意不能在这里求s for(int i=1;i<=n;++i) a[i].x=rd(),a[i].y=rd(); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i].x; f[0][0]=0; for(int i=1;i<=n;++i){ for(int j=s[i];j>=0;--j){ if(j>=a[i].x) f[i][j]=min(f[i][j],max(f[i-1][j-a[i].x],j+a[i].y)); f[i][j]=min(f[i][j],max(f[i-1][j],s[i]-j+a[i].y)); //if(f[i][j]==168430090) cout<<"oo "; //else cout<<f[i][j]<<" "; } //cout<<endl; } int ans=999999999; for(int i=0;i<=s[n];++i) ans=min(ans,f[n][i]); cout<<ans<<endl; return 0; } ```