题解 | 蹄球锦标赛-牛客假日团队赛1A题

https://ac.nowcoder.com/acm/contest/918/A

A. 蹄球锦标赛

题目描述

为了准备即将到来的蹄球锦标赛，Farmer John正在训练他的N头奶牛（方便起见，编号为1…N，其中1≤N≤100）进行传球。这些奶牛在牛棚一侧沿直线排列，第i号奶牛位于距离牛棚x_i的地方(1≤x_i≤1000)。每头奶牛都在不同的位置上。

在训练开始的时候，Farmer John会将若干个球传给不同的奶牛。当第i号奶牛接到球时，无论是从Farmer John或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。

输入描述:

输入的第一行包含N。第二行包含N个用空格分隔的整数，其中第i个整数位x_i

输出描述:

输出Farmer John开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。

示例1

输入

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可以将球传给她之后所有奶牛最终都能被传到球。

解答

给你N个点N条有向边，求在某些点开始跑边能够遍历整张图的最少点数

这已经是简化版的题意了，略去了前面没必要讲的建边（因为对于一个能看懂并写出AC代码的大佬来说这不是啥问题），建边唯一的坑点就是任意一头牛的左右两头牛距离相同连向左边（原题面括号那一句写错了）。

具体讲后面的操作：

如果一个点x连向y一条有向边，那么显然放在x比放在y更优，因为放x一定到y，放y不一定能到x。

我们不妨做出一个假设：只有没有有向边连到的点是需要放球的

这已经非常接近正解了，但是很可惜，少考虑了一种情况

我们考虑这组数据

4
1 3 1 4

这样子相当于构造出了两个大小为二的环（事实上本题最大环大小就是二，但这不是重点，所以读者可以自证）

这样子显然要输出2，但是我们刚刚那样写会输出0

我们意识到应该把所有的环消除掉（比如缩成一个点）

所以我们使用tarjan缩点（可以参考洛谷或者其他OJ的题目，这里不过多说明）将图变为DAG（有向无环图）

然后统计一下有多少入度为0的点即可

时间复杂度：建边O(nlogn)，缩点O(n)

总时间O(nlogn)

（可能有多余变量或数组，直接无视就好了）

#include<iostream>  #include<queue> #include<algorithm> #define maxn 100001  #define t edge[i].to #define s edge[i].nex using namespace std; struct Edge { int to,nex;
}edge[maxn],edg[maxn]; int st[maxn],dis[maxn],DFN[maxn],LOW[maxn],dye[maxn],vis[maxn],size[maxn],stack[maxn],sta[maxn],degree[maxn],dist[maxn],x1[maxn],y2[maxn]; int n,m,cnt,stacksize,color,dfsnum,c,a[2001],maxx; void addedge(int x,int y) {
    edge[++cnt].to=y;
    edge[cnt].nex=st[x];
    st[x]=cnt;
} void tarjan(int start) {
    vis[stack[++stacksize]=start]=1;
    LOW[start]=DFN[start]=++dfsnum; for(int i=st[start];i;i=s) if(!DFN[t])tarjan(t),LOW[start]=min(LOW[start],LOW[t]); else if(vis[t])LOW[start]=min(LOW[start],DFN[t]); if(DFN[start]==LOW[start])
    { int y; while(y=stack[stacksize--])
        {
            dye[y]=start;
            vis[y]=0; if(start==y)break;
            dis[start]+=dis[y];
        }
    }
} int main() { cin>>n;
    m=n; for(int i=1;i<=n;i++)
    { cin>>a[i];
    }
    sort(a+1,a+1+n);
    addedge(1,2);
    x1[1]=1;y2[1]=2;
    x1[n]=n;y2[n]=n-1;
    addedge(n,n-1); for(int i=2;i<n;i++)
    { if(a[i]-a[i-1]<=a[i+1]-a[i])addedge(i,i-1),x1[i]=i,y2[i]=i-1; else addedge(i,i+1),x1[i]=i,y2[i]=i+1;
    } for(int i=1;i<=n;i++)if(!DFN[i])tarjan(i); for(int i=1;i<=m;i++)
    { int x=dye[x1[i]],y=dye[y2[i]];
        maxx=max(maxx,max(x,y)); //cout<<x1[i]<<' '<<y1[i]<<' '<<x<<' '<<y<<endl; if(x!=y)
        {
            edg[++c].to=y;
            edg[c].nex=sta[x];
            sta[x]=c;
            degree[y]++;
        }
    } int ans=0; for(int i=1;i<=maxx;i++)
    { //cout<<degree[i]<<endl; if(!degree[i]&&dye[i]==i)ans++;
    } cout<<ans; return 0;
}