帮 帮 我
发布时间：2020-02-11 22:48:50
贴主：qwq
热度：7
正在讨论：P1912 - 最小开支
题目传送门
qwq 2020-02-11
题目的大意如下：众人出游，已知总人数m、二人间价格a和三人间价格b，求在无人风餐露宿的基础上租房间的最低价。
在我看来，这是一个简单的线性规划问题：倘若设双人间的数量为x，三人间的数量为y，即题意转化为：已知2x+3y>=m，1<=x<=m,1<=y=m&&x∈Z,y∈Z，欲求z=ax+by的最小值。易作图如下：
图中黑色实线上方的区域为可行域。分两种情况讨论：当a/b>2/3时，z(min)=(3/m)*b;当a/b<=2/3时，z(min)=(2/m)*a；同时因为房间数量必为整数，故应该注意对3/m和2/m向上取整。
然此做法似乎行不通，不知问题何在。。。望有人解惑，先行谢过。。。。
(0)
qwq 2020-02-11
那啥。。。图片太小的话可以在新标签页打开。。
(0)
易向晚来适 2020-02-12
这个问题不止是你想的那两种情况
(0)
qwq 2020-02-12
？
(0)
关注鲤鱼Liyuu喵 2020-02-20
6个人一组，一组最便宜怎么来很容易解决，剩下的人写if就行
(0)
qwq 2020-02-25
啊，，，，到底还有什么情况呢。。。。。。？
(0)
qwq 2020-03-09
呃啊。。。。现在看这个方法还真是槽点满满
(0)