寻找木头

JD 2022 校招

时问限制:3000MS
内存限制:589824KB
题目描述:
小明和他的伙伴发现了一堆木头排成了一排,一共n个,假设排列在x轴上,最左端的木头的坐标是0，最右端木头的坐标是n,他们想拿走里面最重和最轻的木头各一个,但是他们并不知道是这一堆里的哪一个，因此他们需要挨个测量。现在他们在这排木头的两端,一个人在坐标0，一个人在坐标n,他们只能按顺序测量,即在0位置的人只能依次测量0.1.2,3然后到n,在n位置的人则相反。现在你已经知道每个木头的重量，你可以指挥他们是否继续测显，问两个人一共最少需要多少次测量就可以找到最重和最轻的木头。
输入描述：
第一行一个整数n,1<=n<=1000
第二行n个空格隔开的整数，表示木头的重层,某中任意一个数大小范围是(0.10000].
输出描述：
个整数,表示最少需要测量的次数。

样例1

输入

5
1 5 4 3 2

输出

2

解释:从左测量1,然后测量5,就可以了

样例2
输入:

8
2 1 3 4 S 6 8 7

输出:

4

解释:从左测量2然后测量1,从石测量然后测量8

题解：

一开始我的思路是
找到数组的最大值最小值距离两端的最小距离，如果都距离一端近，就输出两个最小距离的最大值（如样例1）；
如果分别距离首尾近则输出两个最小距离的和（如样例2）；
但如果是最大值最小值都很靠正中间，最大值最小值的之间距离小于最大值最小值距离两边的距离输出两个最小距离的最小值加上两个最大值最小值之间的距离。

想到这里的时候就不对劲了，换一个思路：
还是找数组的最大值最小值距离两端的最小距离，还是上面的判断条件，
但是需要解决上面分类复杂的问题，
如果最大值和最小值之间的距离很大，则是两边输出，如果最大值和最小值之间的距离（abs(maxidx - minidx)）很小，那么适合单边距离的最大值。
那这个距离的阈值怎么找的呢？
首先如何判断最大值最小值之间的距离是大还是小：
如果最大值最小值之间的距离（abs(maxidx - minidx)）大于最大值最小值距离两边的最小值，那么适合两边距离的和；
如果最大值最小值之间的距离（abs(maxidx - minidx)）小于最大值最小值距离两边的最小值，那么适合单边距离的最大值；
到这里思路就明朗起来了。

代码如下：

N = int(input())
list = input().split(' ')

maxidx = list.index(max(list))  # 最大值索引
minidx = list.index(min(list))  # 最小值索引

len = abs(maxidx -minidx) - 1  #最小值和最大值中间的元素个数（左开右开）
if len < N/2:
    out = min(max(maxidx, minidx) + 1, max(N-maxidx, N-minidx))
else:
    out = N - len
print(out)

执行效果：