题目链接: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需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。
输入
4 7 9
输出
1
2
说明
最小移动次数为1——如果Farmer John将位置4的奶牛移动到位置8,那么奶牛们就处在连续的位置7、8、9。最大移动次数为2。例如,位置9的奶牛可以被移动到位置6,然后位置7的奶牛可以被移动到位置5。
备注
输入的数在[1,10^9]范围内。
解题思路
题意:操作最边上的牛,求最小和最大的可能操作数,使得它们处在相邻位置。
思路:如果一开始就是相邻的,那就是0 0;
如果相邻的都只隔一个位置那么,最小就可以直接跳到它们中间,就是1步,例如3 5 7,那么3直接就可以到6 -> 5 6 7,或者7到4 -> 3 4 5;
否则那么最小的就需要2步,都向中间靠拢,最大那就是找到最大的间隔,相互交错向另一端靠拢,例如3 6 10,最大的间隔就是10-6-1=3,就是3,6交错向10靠拢,3 6 10->6 7 10->7 8 10->8 9 10,共需要3步,因为间隔最大为3.
Accepted Code:
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
int x = b - a, y = c - b;
if (x <= 1 && y <= 1)
printf("0\n0\n");
else if (min(x, y) != 2)
printf("2\n%d\n", max(x, y) - 1);
else printf("1\n%d\n", max(x, y) - 1);
return 0;
}