题目描述：
为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 $ N $ 头奶牛（方便起见，编号为 $ 1 \cdots N $ ）进行传球。
这些奶牛在牛棚一侧沿直线排列，第 $ i $ 号奶牛位于距离牛棚 $ x_i $ 的地方。
每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛。
当第 $ i $ 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会将球传给这些奶牛中最左边的那头奶牛。）。
为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。
帮助他求出为了达到这一目的他开始时至少要传出的球的数量。
假设他在开始的时候能将球传给最适当的一组奶牛。
输入格式
输入的第一行包含 $ N $ 。
第二行包含 $ N $ 个用空格分隔的整数，其中第 $ i $ 个整数为 $ x_i $ 。
输出格式
输出 Farmer John 开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。
数据范围
输入样例：
输出样例：
题解：
因为是一个数组，首先先排序。假设以左端点开始传球，那么碰到环的情况一定是一头奶牛距离左侧更近，这时形成一个二元环。碰到二元环的时候消耗加 $ 1 $ ，因为一个环可能是从左边或者右边传过来的。因此如果左右两侧都有的话，消耗为 $ 2 $ 。
可以使用一个标记数组，表示向左传球。这样的话判环就非常简单，只需要比较当前点和左右两侧点的距离就行了。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
bool flag[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
flag[n] = true;
sort(a + 1, a + 1 + n);
for (int i = 2; i <= n - 1; i++)
{
if (a[i] - a[i - 1] <= a[i + 1] - a[i])
{
flag[i] = true;
}
}
int ans = 0;
for (int i = 1; i <= n; i++)
{
if (flag[i] && !flag[i - 1])
{
ans++;
if (i >= 3 && i + 1 <= n && flag[i + 1] && !flag[i - 2])
{
ans++;
}
}
}
cout << ans << endl;
return 0;
}
|