大家好,又见面了,我是你们的朋友全栈君。
题目:https://www.luogu.org/problemnew/show/P2577
可以从只有一个窗口的角度思考出一个贪心结论。就是应当按吃饭时间(不算打饭时间)从大到小排序。这样交换相邻两个不会使答案更优,因为交换的话对其他人无影响,而吃饭时间长的那个人打到饭的时间也靠后了。
记录第一个窗口打完饭的时间在状态里。已知前 i 个人打饭时间和,能算出来第二个窗口打完饭的时间。所以值就可以记录总共的最晚结束时间了!也因为最晚结束时间对于打完饭的时间不是关系很紧密的,所以需要把第一个窗口的所有可能的打完饭的时间对应的结束时间记录下来。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=205,M=N*N,INF=0x3f3f3f3f; int n,f[2][M],ans=INF,lm; struct Node{ int a,b; bool operator< (const Node &v) const { return b>v.b;} }t[N]; int rdn() { int ret=0,fx=1; char ch=getchar(); while(ch>'9'||ch<'0'){ if(ch=='-')fx=-1; ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return ret*fx; } int main() { n=rdn(); for(int i=1;i<=n;i++) t[i].a=rdn(),t[i].b=rdn(); sort(t+1,t+n+1); memset(f,0x3f,sizeof f); f[0][0]=0; for(int i=1,u=1,v=0;i<=n;i++,u=!u,v=!v) { lm+=t[i].a; for(int j=0,k1,k2;j<=lm;j++) { if(f[v][j])f[u][j]=max(f[v][j],lm-j+t[i].b); if(j>=t[i].a) f[u][j]=min(f[u][j],max(f[v][j-t[i].a],j+t[i].b)); } } int d=(n&1); for(int j=0;j<=lm;j++) ans=min(ans,f[d][j]); printf("%d\n",ans); return 0; }
转载于:https://www.cnblogs.com/Narh/p/9670070.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107300.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...