题目描述 小 Z 、小 Y 和小 X是三个无话不谈的好朋友,但是却在这次分座的时候被班主任强哥分到了一排中三个不相邻的位置上。
假设这一排中最左侧到最右侧的座位编号是分别是 1 , 2 , 3... 1,2,3...,小 Z,小 Y 和小 X 正处于这一排中不同座位编号的位置上,而且这一排上只有他们三个人。班主任强哥每周都会调换座位,他们希望能够坐到三个相邻的位置上(例如,位置 3、4、5)。
但是班主任强哥每周只会调换他们三个好朋友中一个人的座位,而且为了让他们体会到友谊的珍贵,只允许让三名同学中坐在最左侧和最右侧的同学调换位置。当到了调换位置的时候,会让允许调换位置的同学指定一个未占用位置来进行调换,但这个位置不允许在端点的位置上。随着一周一周的调换,会让三个好朋友的位置越靠越近。
更通俗一点的说法就是,每次在两端的某一个同学,会去坐到另外两个人中间的空位上。
请求出使得三个好朋友坐到一起的最小周数和最大周数。
输入
输入包含一行,包括三个空格分隔的整数,为小 Z 、小 Y 和小 X 的初始位置。
输出
第一行为坐到一起需要的最小周数。
第二行为坐到一起需要的最大周数。
代码:
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int tot(int l,int k,int h){
if(l==k){
if(l+1==h) return 2;
else return 1;
}else return 0;
}
bool left(int l,int m,int r){
int j=(m+r)/2;
j+=tot(j,m,r);
l=m;
m=j;
if(l+1==m&&m+1==r) return true;
else return false;
}
bool right(int l,int m,int r){
int j=(l+m)/2;
j+=tot(j,l,m);
r=m;
m=j;
if(l+1==m&&m+1==r) return true;
else return false;
}
int MIN(int l,int m,int r,int step){
if(left(l,m,r)) return step+1;
else if(right(l,m,r)) return step+1;
else return min(MIN(m,(m+r)/2+tot((m+r)/2,m,r),r,step+1),MIN(l,(l+m)/2+tot((l+m)/2,l,m),m,step+1));
}
int MAX(int l,int m,int r,int step){
if(l+1==m&&m+1==r) return step;
else return max(MAX(m,(m+r)/2+tot((m+r)/2,m,r),r,step+1),MAX(l,(l+m)/2+tot((l+m)/2,l,m),m,step+1));
}
int main(){
cin>>a>>b>>c;
cout<<MIN(a,b,c,0)<<endl;
cout<<MAX(a,b,c,0)<<endl;
return 0;
}
求MAX超时,为什么