有一部电梯停在第一层，它一次最多能容纳32人，而且只能在第2层至33层中某一层停下来，全部人出来，且中间不停。对每个人来说，往下走一层楼梯感到1分不满意，往上走一层感到3分不满意。现在有32人在第一层，并且他们分别住在第2层至33层的每一层。问电梯停在哪一层，可以使得这32人不满意的总分达到最小？最小值是多少？(有些人可以不乘电梯而直接从楼梯上楼) 并请给出解题的过程。
I am not sure about your logic, but I think there are more cases: people who live in the lower floors may either directly walk upstairs or take the elevator and then walk downstairs. Anyway, it is not hard. |
27th floor |
Let n (2<=n<=33) be the floor that the elevator stopped, D(n) be the total displeased points. Since everyone tried to minimize his displease points, people live at or lower than floor [(n+3)/4] (here, [x] is the largest integer less than or equal to x) will walk, all others will take the elevator. If n+3 = 0 (mod 4), the person lives at floor (n+3)/4 is indifferent, so we assume he/she will always take the elevator.
Consider D(n+1)-D(n) (2<=n<=32), then we only have to consider those taking the elevator. Let the total displease points for those walking be S. D(n+1) = 3(1+…+(33-n-1))+(1+…+(n+1-[(n+3)/4])) + S D(n) = 3(1+…+(33-n))+(1+…+(n-[(n+3)/4])) + S So D(n+1)-D(n) = (n+1-[(n+3)/4])-3(33-n) = 4n-98-[(n+3)/4] It’s negative when n < 27, positive when n >= 27.
That means floor 27 is the best choice. The total displease points are 3(1+…+6)+(1+…+19)+3(1+…+5) = 63 + 190 + 45 = 298. |
a trivial error: The total displease points are 3(1+…+6)+(1+…+19)+3(1+…+5+6) = 63 + 190 + 63= 316. |
设停在n层。 如果没有自己上楼的，大家都坐电梯，就是1：3分配32个人，n=24） 如果有自己上楼的 1，总有至少 『n/4』个人需要爬楼。这些人不管它，让他们自己爬 (这部分人满足和最小） 2，坐电梯的人，分成两部分，下楼的和上楼的。 比例自然是 1：3 （这部分满足和最小） 所以 『 32－n』 : 『3n/4 － n/4』 = 1:3 即 (32－n)/ ( 1/2n)=1/3 取整 解得n=27 |
设停在n层。 如果没有自己上楼的，大家都坐电梯，就是1：3分配32个人，n=24） （转自：顶顶华闻 www.TopChineseNews.com ）如果有自己上楼的 1，总有至少 『n/4』个人需要爬楼。这些人不管它，让他们自己爬 (这部分人满足和最小） 2，坐电梯的人，分成两部分，下楼的和上楼的。 比例自然是 1：3 （这部分满足和最小） 所以 『 33－n』 : 『3n/4』 = 1:3 取整 解得n=27 刚才一着急打错了。 |
| 欢迎光临 珍珠湾ART (http://zzwav.com/) | Powered by Discuz! X3 |