Hoofball 题解

题面:

翻译:

农夫有N头奶牛在训练踢球,他们站成一排,位置分别是x1,x2…xn(xi越大,位置越靠右).
每当一头奶牛接到一个球后,他会传给和他距离最短的奶牛
如果有两头奶牛和他距离相同,那么他就会传给左边的奶牛.
农夫要发多少个球,才能使所有的奶牛都至少能够碰到一次球.

输入:

第一行是一个整数n,代表有多少头奶牛
第二行是n个整数,分别代表n头奶牛的位置.

输出:

一个整数,农夫至少需要发多少个球?

题目分析:

在输入了所有奶牛的位置之后,我们先把他们从左到右排序,以方便之后的处理.
之后我们知道,最左边的奶牛一定会传给他右边的那一头奶牛.
最右边的奶牛一定会传给他左边的那一头奶牛.
然后在判断从左到右的第二到倒数第二头奶牛分别会把球传给谁?然后用一个变量to来记录
同时用一个变量from记录下每一头奶牛能够收到多少头奶牛传给他的球.

这样处理之后,开始传球.
用一个数组shuted来记录每一头奶牛是否碰到过球.

从左到右找到每一头from为0并且没有碰过球的奶牛,给他传一个球,然后再让他继续传下去,标记每一个碰到球的奶牛.

按照以上的方法传完一遍之后,从左到右找到所有仍然没有碰过球的奶牛,给他们传一个球,再然他们一直传下去.标记每一个碰到球的奶牛.

这样就可以得到要传多少个球.

代码:

#include<stdio.h>
#include<algorithm>

class cow{
public:
    int to = 0, from = 0;
}ccows[150];

int n, ans, cows[150];
int shoted[150];

void shot(int i){
    shoted[i] = 1;
    if(!shoted[ccows[i].to])   shot(ccows[i].to);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)  scanf("%d", cows+i);

    std::sort(cows+1, cows+n+1);

    ccows[1].to = 2;ccows[2].from += 1;
    ccows[n].to = n-1;ccows[n-1].from += 1;
    for(int i = 2; i < n; ++i){
        if(cows[i] - cows[i-1] <= cows[i+1] - cows[i]){
            ccows[i].to = i-1;
            ccows[i-1].from += 1;
        }else{
            ccows[i].to = i+1;
            ccows[i+1].from += 1;
        }
    }
    for(int i = 1; i <= n; ++i){
        if(!shoted[i] && !ccows[i].from){
            shot(i);
            ans++;
        }
    }
    for(int i = 1; i <= n; ++i){
        if(!shoted[i]){
            shot(i);
            ans++;
        }
    }
    printf("%d", ans);
}