摘要
Title: 1738. 蹄球
Tag: 基环树、思维
Memory Limit: 64 MB
Time Limit: 1000 ms

1738. 蹄球

题意

为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 N 头奶牛（方便起见，编号为 1…N）进行传球。
这些奶牛在牛棚一侧沿直线排列，第 i 号奶牛位于距离牛棚 xi 的地方。
每头奶牛都在不同的位置上。
在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛
当第 i 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会将球传给这些奶牛中最左边的那头奶牛。）。
为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。
帮助他求出为了达到这一目的他开始时至少要传出的球的数量。
假设他在开始的时候能将球传给最适当的一组奶牛。
思路

模型：基环树：n个点n条边的连通图，可以发现只有一个环，并且删掉环上任意一个边可以变成一棵树

可以发现此题，每个点一定会连向下一个边，或者向左走，或者向右走，说明每个点的出度 $=1$ ，入度 $\le 2$ ，那么将数组排序，分清每个点会往哪走之后，会呈现出多个连通块，连通块有下面几种情况：
- 一条链
  即如果一直右边的差小于左边的差，那么会成一条链，那么只需要在起点放球即可，即入度 $=0$ 的点（每个点贡献为1）
- 环
  当连通块只有两个点时，球就会在两个点中反复横跳，故只需放其中一个点即可（每个点贡献为 $\frac {1} {2}$ ）
- 特殊的基环树（环只有两个点）
  当排除一直往右走的情况，那么必定会某一时刻往左走，那么这两个点就会形成环，也就是形成特殊的基环树，两个环上的点都最多有一个树枝，那么只需在树枝起点放球即可，即入度 $=0$ 的点（每个点贡献为1）
所以可以合并1，3情况，每个需要计数的点贡献+2；第二种情况贡献+1；结果最后整除2即可

例子

10
384 887 778 916 794 336 387 493 650 422

代码

'''
Author: NEFU AB-IN
Date: 2022-02-10 09:29:20
FilePath: \ACM\Acwing\1738.py
LastEditTime: 2022-02-10 10:14:41
'''
N = 110
p = [0 for _ in range(N)]  #表示第i个点下一个走的点的坐标为p[i]
deg = [0 for _ in range(N)]  #入度
INF = int(2e9)

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    if n <= 2:
        print(1)
        exit(0)
    a.sort()
    a = [-INF] + a + [INF]
    for i in range(1, n + 1):
        if a[i] - a[i - 1] <= a[i + 1] - a[i]:
            p[i] = i - 1
            deg[i - 1] += 1
        else:
            p[i] = i + 1
            deg[i + 1] += 1
    res = 0
    for i in range(1, n + 1):
        if not deg[i]:
            res += 2
        elif p[p[i]] == i and deg[i] == 1 and deg[p[i]] == 1: #判断是否只存在一个环
            res += 1
    print(res // 2)

1738. 蹄球

题意

思路

代码