题解

第三题：

读题：

给定一串数列，求至少将相邻两个数字交换几次，才能够让整个数列变成头最大、尾最小的数列

---

思路：

这是全场最难的题！
想象一下，模拟做法有多么困难，又有多么容易超时！
那么我们可以转变为递推（像我给的新春欢乐赛第一题题解一样），找到一个规律
我们发现，能够擂台找到最大值的位置和最小值的位置，把最大值移到头需要abs(maxi-0)次，最小值移到尾需要abs(mini-(n-1))次
但是有没有想过最小的会在最大的前面？那如果这时我要把最大值放到最前面时，必须要和最小值交换一次，那么就需要减少一次！
还有一个问题：当有并列最大值或最小值时，我们选哪一个？
对于这个问题，我们再看一下题目：要求交换次数尽可能少，那么因为最大值要移到队首，所以我们最好选最靠前的最大值；同理，我们应该选最靠后的最小值。

---

代码：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,s[100];
int main(){
    cin>>n;
    int maxn=0,maxi=0,minn=2147483647,mini=0;
    for(int i=0;i<n;i++){
        cin>>s[i];
        if(s[i]>maxn)maxn=s[i],maxi=i;
        if(s[i]<=minn)minn=s[i],mini=i;
    }cout<<abs(mini-(n-1))+abs(maxi-0)-(mini<maxi);
    return 0;
}

---

---