当前位置: 首页 > news >正文

[题解]meal

题目描述

下课铃终于响了,你和一群朋友(共 N 人)一起冲到食堂。因为你们到的非常早,现在食堂窗口前面还没有人。食堂共有两个窗口。你们每个人打饭会耗时 a i,打完立刻去座位上吃饭会耗时 b i,由于你们吃完饭要一起打球,所以你们希望最后一个人吃完饭的时间尽可能早。现在,你要安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

输入格式

第一行一个整数 N ,表示共有 N 人。
接下来 N 行,每行两个整数a i​,b i​,表示每个人打饭和吃饭的用时。

输出格式

一个整数,表示所有人吃完饭的最早时间。

输入输出样例

输入

5
2 2
7 7
1 3
6 4
8 5

输出

17

思路:

这是一个经典问题(“午餐”问题),最优策略是:

  • 将人按 ( b_i ) 从大到小排序。
  • 用 DP:( f[i][j] ) 表示前 i 个人,第一个窗口总打饭时间为 j 时,所有前 i 个人中最晚结束时间的最小值。

转移方程

初始化

[ f[0][0] = 0 ]

转移

  • 放入窗口1:

    • 第一个窗口总时间 = j
    • 此人结束时间 = ( j + b_i )
    • 之前最晚结束时间 = ( f[i-1][j - a_i] )
    • 新的最晚结束时间 = ( \max(f[i-1][j - a_i], j + b_i) )
  • 放入窗口2:

    • 第一个窗口总时间 j 不变
    • 第二个窗口总时间 = ( \text{sumA}[i-1] - j )
    • 此人结束时间 = ( (\text{sumA}[i-1] - j) + b_i )
    • 新的最晚结束时间 = ( \ max(f[i-1][j], (\text{sumA}[i-1] - j) + b_i) )

算法步骤

  1. 按 ( b_i ) 从大到小排序
  2. 初始化 DP 数组
  3. 遍历每个人,更新 DP 状态
  4. 最终答案为 ( \min(f[n][j]) ) 对所有 j

代码:

#include<bits/stdc++.h>
using namespace std;
struct s{int a,b;
}p[505];
int n,c,y,f[2][250005];
bool cmp(s x,s y)
{return x.b>y.b;
}
int main(){/*freopen("meal.in","r",stdin);freopen("meal.out","w",stdout);*/scanf("%d",&n);int t=0;for (int i=1;i<=n;i++){scanf("%d%d",&p[i].a,&p[i].b);t+=p[i].a;}sort(p+1,p+n+1,cmp);memset(f,0x3f,sizeof(f));f[0][0]=0;for(int i=1;i<=n;i++){c^=1;memset(f[c],0x3f,sizeof(f[c]));y+=p[i].a;for(int j=0;j<=y;j++){//放入窗口1if (j>=p[i].a){f[c][j]=min(f[c][j],max(f[c^1][j-p[i].a],j+p[i].b));}//放入窗口2f[c][j]=min(f[c][j],max(f[c^1][j],(y-j)+p[i].b));}}int ans=INT_MAX;for(int i=0;i<=t;i++){ans=min(ans,f[c][i]);}printf("%d",ans);return 0;
}
http://www.hskmm.com/?act=detail&tid=36513

相关文章:

  • CADSoftTools发布两款重要更新:CAD VCL Multiplatform 16.2 与 CAD .NET 16全新发布
  • linux常用命令 - 实践
  • 2025年10月河道防撞护栏厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • 在 Linux 系统上安装 Miniconda、安装 Xinference,并设置 Xinference 开机自启动
  • 作业三(结对编程)-小学四则运算题目生成与判卷(Python + 可视化)
  • 无穷小比较、等价无穷小替换
  • 【项目复现上新】Karpathy大神开源GitHub高分项目NanoChat!仅用100美元+8000行代码手搓ChatGPT
  • CF2159E
  • 2025年10月景区钢丝绳护栏厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • 技术 | 在单台电脑上管理多个 GitHub 账户并解决推送问题(测试中)
  • Stable Diffusion启动提示端口错误处理
  • 阿里云API网关日志问题
  • 2025年10月半封闭滑轨丝杆模组厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • ipad协议对个人微信机器人进行二次开发
  • 西安交通大学国家级医学公关交叉平台实验室建设实拍图
  • 小程序-定义头部导航
  • 2025年10月简易丝杆模组定制厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • 2025年10月智能门窗代理厂家全景解析报告,基于专业测评的技术、性能及市场优势深度分析
  • Android插件化框架
  • 2025 年烧结砖厂家最新推荐榜单权威发布:四川蜀陶领衔企业,全方位解决采购难题,为建筑项目保驾护航铺地砖/劈开砖/陶土窗花/古建筑砖瓦厂家推荐
  • Java使用Graphics2D绘图在图片插入中文字符放到Linux上面运行时图片中的中文会变成方框或乱码的问题
  • 2025年最新喷码机厂家推荐榜:激光/UV/手持喷码机十大品牌全解析
  • Golang的 cron 库
  • 实用指南:Linux 如何创建和计数套接字
  • 中小企业如何低成本部署电话呼叫软件网页版?一步步教你做
  • 别再手写过滤器!SpringCloud Gateway 内置30 个,少写 80% 重复代码
  • 记一次 .NET 某药品缺陷高速检测系统 卡慢分析
  • 0254-CLAP-参数默认值
  • 得物火山引擎:Data Agent驱动财务管理智能升级
  • WPF/C#:使用Stylet中的IWindowManager用于显示等待窗体、对话框与消息框