首页 > 代码库 > sicily 1193. Up the Stairs
sicily 1193. Up the Stairs
Time Limit: 1sec Memory Limit:32MB Description John is moving to the penthouse of a tall sky-scraper. He packed all his stuff in boxes and drove them to the entrance of the building on the ground floor. Unfortunately the elevator is out of order, so the boxes have to be moved up the stairs. Luckily John has a lot of friends that want to help carrying his boxes up. They all walk the stairway at the same speed of 1 floor per minute, regardless of whether they carry a box or not. The stairway however is so narrow that two persons can‘t pass each other on it. Therefore they deciced to do the following: someone with a box in his hands is always moving up and someone empty-handed is always moving down. When two persons meet each other somewhere on the stairway, the lower one (with a box) hands it over to the higher one (without a box). (And then the lower one walks down again and the higher one walks up.) The box exchange is instantaneous. When someone is back on the ground floor, he picks up a box and starts walking up. When someone is at the penthouse, he drops the box and walks down again. After a while the persons are scattered across the stairway, some of them with boxes in their hands and some without. There are still a number of boxes on the ground floor and John is wondering how much more time it will take before all the boxes are up. Help him to find out! Input One line with a positive number: the number of test cases. Then for each test case:
Output One line with the amount of time (in minutes) it will take to get all the remaining boxes to the penthouse. Sample Input Copy sample input to clipboard 23 10 50 00 00 02 5 12 13 0 Sample Output 308 |
首先这个可以看成一组人在移动,因为它的交换物品与方向跟没交换的效果是一样的。另外考虑的就是,搬一个新的物品比已经在楼梯上的人来说它的速度总是更慢的。所以在搬运期间,还没到最后一趟的时候,大家搬运的个数是一样的,所以可以用 (boxNum / personNum - 1) * 2 来计算在这期间的时间,剩下的就是初始状态在楼梯上和最后一趟的时间的考虑了。
#include <iostream>#include <algorithm>using namespace std;int main(int argc, char const *argv[]){ int testCase, personNum, floorNum, boxNum, floor, cally; int person[1001]; cin >> testCase; while (testCase--) { cin >> personNum >> floorNum >> boxNum; for (int i = 0; i != personNum; ++i) { cin >> floor >> cally; if (cally == 0) person[i] = floorNum + floor; else person[i] = floorNum * 3 - floor; } sort(person, person + personNum); int remain = boxNum % personNum; int minute = 0; if (remain == 0) { minute = (boxNum / personNum - 1) * 2 * floorNum + person[personNum - 1]; // 上到顶端就不需要再下来了,所以 -1 } else { minute = (boxNum / personNum) * 2 * floorNum + person[remain - 1]; // 上到顶端后还需要下来搬运剩下的 } cout << minute << endl; } return 0;}
sicily 1193. Up the Stairs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。