鏈接：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]范圍內

題意：

思路：
最小的操作次數一定是1或2，看解釋：

如果有兩個牛相隔一個數，那么最小只需要一步就可以完成操作。

否則最小只需要兩步即可。

第一步移動一個端點的牛到與另外一個牛相隔一個數的位置，

第二步讓另一個端點的牛移動到那個中間的位置即可。。

最大的就輸出兩個相鄰的牛之間最大個間隔數。

細節見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int* p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ll a[50]; int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;int n=3;repd(i,1,n){cin>>a[i];}sort(a+1,a+1+n);if(min(a[2]-a[1],a[3]-a[2])-1==0){cout<<min(2ll,max(a[2]-a[1],a[3]-a[2])-1)<<endl;}else{cout<<min(2ll,min(a[2]-a[1],a[3]-a[2])-1)<<endl;}cout<<max(a[2]-a[1],a[3]-a[2])-1<<endl;return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11284811.html

總結

以上是生活随笔為你收集整理的牛客假日团队赛6 D迷路的牛 （思维）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。