链接：

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

题意：

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

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

思路：

将位置排成一条线，第一头牛只能向右边传球，最后一头牛只能向左边传球。

如果两头相邻的牛，左边只能向右边传，右边只能向左边传，则球的数量加1，同时，再左边一个只能向右边传，再右边只能向左边传，球数再加1。即>><<这种传球顺序，需要两个球。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e3 + 10;

const int MOD = 1e9 + 7;

int n, m, k, t;

int a[MAXN];

int b[MAXN];

int to[MAXN];

int main()

{

    cin >> n;

    for (int i = 1;i <= n;i++)

        cin >> a[i];

    sort(a+1, a+1+n);

    for (int i = 1;i < n;i++)

        b[i] = a[i+1]-a[i];

    to[1] = 1;

    to[n] = -1;

    for (int i = 2;i < n;i++)

    {

        if (b[i] >= b[i-1])

            to[i] = -1;

        else

            to[i] = 1;

    }

    int res = 0;

    for (int i = 1;i < n;i++)

    {

        if (to[i] == 1 && to[i+1] == -1)

        {

            res++;

            if (to[i-1] == 1 && to[i+2] == -1)

                res++;

        }

    }

    cout << res << endl;

    return 0;

}

巴特西

牛客假日团队赛1 A.蹄球锦标赛

链接：

题意：

思路：

代码：

最新文章

热门文章