【基环树+思维】AcWing 1738.蹄球——每日一题2.6

题目链接

1738. 蹄球 - AcWing题库

题意

给出$n(1\leq n\leq 100)$头牛，每头牛有自己的位置$x_i(1\leq x_i\leq 1000)$。每头牛给两侧相邻的牛传球，规定是传给距离较小的那个，如果相同则选左边的，每个牛都需要传一次球，你可以一开始在若干个牛上放球，然后开始传，问开始需要放置多少个球使得所有牛都持球一次。

思路

有$n$个点，每个点传一次（这个是固定的），就是$n$条边。

$n$个点，$n$条边 —— 基环树

所以，这里面是若干个基环树，为什么说若干的，是因为有可能它不连通，所以我们分为两种情况：

1）左边的情况是基环树，一棵环上接了很多树：
我们需要统计入度为$0$的，也就是d[i]==0的时候，这个时候我们需要放一个球，因为没有其他地方可以传入，每个入读为$0$的点的贡献是1

2）右边的情况就是单独的一个奇环：
我们只需要一次就可以传遍这两个，我们在for循环的时候每个点的贡献是0.5，为了整数计算，我们可以选择+1之后让i++达到continue效果，也可以+1并且让第一种情况的贡献+2，最后输出的时候除以$2$即可

基环树

代码

1）思维计算贡献

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    a[0]=-inf;a[n+1]=inf;//这样可以让第一个点传给第二个，最后一个给前一个
    for (int i=1;i<=n;i++)
    {
        if (a[i]-a[i-1]>a[i+1]-a[i]) e[i]=i+1,d[i+1]++;
        else e[i]=i-1,d[i-1]++;//e[i]统计传给哪个点,d[i]统计入度
    }
    for (int i=1;i<=n;i++)
        if (e[e[i]]==i&&d[i]==1&&d[e[i]]==1) ans++;//第二种情况，两个点的环，入度均为1
        else if (!d[i]) ans+=2;
    cout<<ans/2;
}

2）拓扑思想dfs

inline void dfs(int x)
{
    vis[x]=1;
    if (!vis[e[x]]) dfs(e[x]);
}//dfs用来遍历可以达到的
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    e[1]=2;e[n]=n-1;
    for (int i=2;i<n;i++)
    {
        if (a[i]-a[i-1]>a[i+1]-a[i]) e[i]=i+1;
        else e[i]=i-1;
    }
    for (int i=1;i<=n;i++) ind[e[i]]++;
    for (int i=1;i<=n;i++)
        if (!ind[i]) ans++,dfs(i);//拓扑 第一种情况，入度为0就开始放置球遍历
    for (int i=1;i<=n;i++)
        if (!vis[i]) ans++,dfs(i);//还没有达到的 也需要放球，这个就是第二种情况
    cout<<ans;
}