牛客假日团队赛6 D：迷路的牛

链接：https://ac.nowcoder.com/acm/contest/993/D
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

Farmer John的三头获奖奶牛Bessie、Elsie和Mildred，总是会迷路走到农场上遥远的地方去！他需要你帮助将她们一起赶回来。

农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。这3头奶牛现在正位于不同的整数位置，Farmer John想要移动她们，使得她们占据三个相邻的位置（例如，位置6、7、8）。

不幸的是，奶牛们现在很困，Farmer John要让她们集中精力听从命令移动并不容易。任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。

请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。

输入描述:

输入包含一行，包括三个空格分隔的整数，为Bessie、Elsie和Mildred的位置。每个位置均为一个范围1…10^9内的整数。

输出描述:

输出的第一行包含Farmer John需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。

示例1

输入

复制

4 7 9

输出

复制

1

2

说明

最小移动次数为1——如果Farmer John将位置4的奶牛移动到位置8，那么奶牛们就处在连续的位置7、8、9。最大移动次数为2。例如，位置9的奶牛可以被移动到位置6，然后位置7的奶牛可以被移动到位置5。

备注:

输入的数在[1,10^9]范围内

 解题思路：

当有两个奶牛的位置相差2的时候，可以把另一个直接插入中间，最短需要1步，而其他的情况最短是都是2步。

如果是求最长步数，则是相邻的两头奶牛距离差的最大值-1，

比如2 7 9

把9移动到3变为2 3 7

把2移动到6变为3 6 7

把7移动到4变为3 4 6

把3移动到5变为4 5 6

一共7-2-1=4中可能，因为2到7中只有4个数可以移动。

#include <stdio.h>

#include <algorithm>

using namespace std;

#define N 20

int a[N];

int main()

{

int i, maxi;

for (i = 0; i < 3; i++)

scanf("%d", &a[i]);

sort(a, a + 3);

if (a[1] - a[0] == 1 && a[2] - a[1] == 1)

printf("0n0n");

else {

if (a[1] - a[0] == 2 || a[2] - a[1] == 2)

printf("1n");

else

printf("2n");

maxi = max(a[1] - a[0], a[2] - a[1]);

printf("%dn", maxi-1);

}

return 0;

}

相关知识

宠物文化 14.牛 牛的种类与分布.doc
QQ宠物玩嘉年华中的牛翔赛跑赛场有什么诀窍？
病牛的消化、泌尿系统及外生殖器的检查方法
2024石牛山·绳命LifeLine国际绳索救援邀请赛在石牛山启幕
法牛个人领养 家养纯种法牛 奶油色黑色蓝色法牛 宠物狗 疫苗驱虫已做
牛嘴笼的制作方法
牛呼吸道疾病
饥荒驯牛攻略，饥荒训牛的时候牛发情了怎么办？
青苹果蜗牛、五基因暴牛、除臭技术牛……这届亚宠展还挺“牛”
传说中的“赛级犬” 究竟有多牛？

网址: 牛客假日团队赛6 D：迷路的牛 https://www.mcbbbk.com/newsview522431.html