| 题目名称 | 3029. [USACO Feb18 Bronze]Hoofball |
|---|---|
| 输入输出 | hoofball_bronze_18feb.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Benjamin
于2018-10-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：3， 提交：20， 通过率：15% | ||||
 ┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
|
梦那边的美好ET |
100 | 0.002 s | 0.32 MiB | C++ |
|
Benjamin |
100 | 0.003 s | 0.31 MiB | C++ |
|
aaaa1218 |
60 | 0.002 s | 0.33 MiB | C++ |
|
梦那边的美好ET |
60 | 0.003 s | 0.32 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
10 | 0.000 s | 0.00 MiB | C++ |
|
梦那边的美好ET |
10 | 0.002 s | 0.32 MiB | C++ |
|
aaaa1218 |
10 | 0.002 s | 0.33 MiB | C++ |
 Gordon5566 |
10 | 0.003 s | 0.37 MiB | C++ |
| 本题关联比赛 | |||
| 近期练习题回顾 | |||
| 关于 Hoofball 的近10条评论(全部评论) |
|---|
3029. [USACO Feb18 Bronze]Hoofball
★☆ 输入文件：hoofball_bronze_18feb.in
输出文件：hoofball_bronze_18feb.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
为了准备即将到来的蹄球锦标赛，Farmer John正在训练他的N头奶牛（方便起见，编号为1…N，其中1≤N≤100）进行传球。这些奶牛在牛棚一侧沿直线排列，第i号奶牛位于距离牛棚xi的地方(1≤xi≤1000)。每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John会将若干个球传给不同的奶牛。当第i号奶牛接到球时，无论是从Farmer John或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。
【输入格式】
输入的第一行包含N。第二行包含N个用空格分隔的整数，其中第i个整数为xi。
【输出格式】
输出Farmer John开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。
【样例输入】
5 7 1 3 11 4
【样例输出】
2
【提示】
在上面的样例中，Farmer John应该将球传给位于x=1的奶牛和位于x=11的奶牛。位于x=1的奶牛会将她的球传给位于x=3的奶牛，在此之后这个球会在位于x=3的奶牛和位于x=4的奶牛之间来回传递。位于x=11的奶牛会将她的球传给位于x=7的奶牛，然后球会被传给位于x=4的奶牛，在此之后这个球也会在位于x=3的奶牛和位于x=4的奶牛之间来回传递。这样的话，所有的奶牛都会至少一次接到球（可能从Farmer John，也可能从另一头奶牛）。
可以看出，不存在这样一头奶牛，Farmer John可以将球传给她之后所有奶牛最终都能被传到球。
【来源】
USACO 2018 February Contest Bronze problem 2
供题：Dhruv Rohatgi