当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1931:Target Practice

题目描述
There are many forms of contests where the contestants (shooters) try to hit targets, either moving or still. In this version there are a number of small balloons sitting on the tops of poles that are in turn stuck in the ground at various points in a large field. These poles are not all the same height. The shooter circles the field and fires at the balloons, the goal being to burst all the balloons with as few shots as possible. Since the balloons offer almost no resistance to a bullet, the bullet will pass right through and possibly hit one or more other balloons. So, by judiciously taking shots, the shooter might need only a very few shots to hit all the targets (provided the shooter is a good marksman, which we will assume is the case).
For example, the following field of 10 targets can be covered in only four shots, as shown. (The first two numbers at each position indicate the position of the balloon, and the third number the height.)

Your job is to determine the fewest number of shots necessary to hit all the targets in a given field.
输入解释
There will be multiple test cases. Each test case will consist of an integer n (<= 50) indicating the number of target positions to follow. A value of n = 0 indicates end of input. There will follow n integer triples, x y h, indicating a balloon at position (x, y) in the field at height h. (There will be at most one balloon at any position (x, y).) All integers are greater than 0 and no greater than 100. Furthermore assume that the shooter can take shots from anywhere on the field at any height. For simplification, assume here that the balloons are points and that the bullets can pass through the poles on which the balloons are perched.
输出解释
Each test case should produce one line of output of the form:
Target set k can be cleared using only s shots.
where k is the number of the test case, starting at 1, and the value of s is the minimum number of shots needed to hit all the targets in the set.
输入样例
10
5 15 4 10 60 52 17 27 4 33 20 10 33 85 31 42 52 4 70 70 22
78 88 4 85 40 58 100 75 7
9
5 15 4 10 60 52 17 27 4 33 20 10 33 85 31 42 52 4 70 70 22
78 88 4 100 75 7
0
输出样例
Target set 1 can be cleared using only 4 shots.
Target set 2 can be cleared using only 3 shots.
来自杭电HDUOJ的附加信息
Recommend 威士忌

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-1931

最后修改于 2020-10-25T22:48:59+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
5000/1000MS(Java/Others) 32768/32768K(Java/Others)