若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1579: Ferry Loading

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,070

题目描述

Ferries are used to transport cars across rivers and other bodies of water. Typically, ferries are wide enough to support two lanes of cars throughout their length. The two lanes of cars drive onto the ferry from one end, the ferry crosses the water, and the cars exit from the other end of the ferry.

The cars waiting to board the ferry form a single queue, and the operator directs each car in turn to drive onto the port (left) or starboard (right) lane of the ferry so as to balance the load. Each car in the queue has a different length, which the operator estimates by inspecting the queue. Based on this inspection, the operator decides which side of the ferry each car should board, and boards as many cars as possible from the queue, subject to the length limit of the ferry. Write a program that will tell the operator which car to load on which side so as to maximize the number of cars loaded.

输入

The input begins with a single positive integer on a line by itself indicating the number of test cases, followed by a blank line.

The first line of each test case contains a single integer between 1 and 100: the length of the ferry (in meters). For each car in the queue there is an additional line of input specifying the length of the car in cm, an integer between 100 and 3,000 inclusive. A final line of input contains the integer 0. The cars must be loaded in order, subject to the constraint that the total length of cars on either side does not exceed the length of the ferry. As many cars should be loaded as possible, starting with the first car in the queue and loading cars in order until the next car cannot be loaded.

There is a blank line between each two consecutive inputs.

输出

The input begins with a single positive integer on a line by itself indicating the number of test cases, followed by a blank line.

The first line of each test case contains a single integer between 1 and 100: the length of the ferry (in meters). For each car in the queue there is an additional line of input specifying the length of the car in cm, an integer between 100 and 3,000 inclusive. A final line of input contains the integer 0. The cars must be loaded in order, subject to the constraint that the total length of cars on either side does not exceed the length of the ferry. As many cars should be loaded as possible, starting with the first car in the queue and loading cars in order until the next car cannot be loaded.

There is a blank line between each two consecutive inputs.

样例输入

1

50
2500
3000
1000
1000
1500
700
800
0


样例输出

6
port
starboard
starboard
starboard
port
port


参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 Skip 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist