CF1538A Stone Game

题目大意

传送门

给串有标号石头，摧毁其中的最大值和最小值，每次只能从最左和最优最右摧毁一个，问最少需要摧毁多少个石头。

分析

这道题是一个模拟题，我们可以先找到最大值和最小值石头的编号，然后从两个石头中选出一个离序列两端最近的石头催毁，再找到另一个石头在新序列中离两端最小的距离进行统计，输出结果即可。

注意：

摧毁石头也要计一次数。

细节优化1

因为我们不知道最大值和最小值石头的序列的先后顺序，可能要判断许多种情况，会相当麻烦。

但是，我们思考一下，为什么要找最大值和最小值？

是为了存他们的坐标，那存了之后，我们眼中就只剩坐标了！所以存坐标后，如果最小值坐标在最大值坐标之后，可以用 swap 将两者替换，这样可以省去许多无谓的判断。

细节优化2

再找最大值与最小值时，我们可以不存序列，边读边存，因为我们要的只是坐标。

细节优化3

我们可能会碰见如下情况：最大值与最小值离两端的最小距离相同。但这并不影响我们。

例子：

• $2,1,3,5,6,4$
• $3,2,1,6,5,4$

我们可以发现他们离两端的距离都为 $1$（第二个是 $2$），但是如果我们可以发现，不管我们先摧毁那个石头，另一个石头在新序列中离两端的最近距离不受影响。

代码

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cmath>
using namespace std;
int t,n;//t组数据，n个石头 
int x;//当前石头的数值 
int m_i,m_a;//最小值与最大值 
int i_x,a_x;//最小值与最大值坐标 
int ans;//答案 
int n_i,n_a;//找到两个坐标分别离两端的最短距离 
int main(){
  scanf("%d",&t);
  while(t--){
    m_a=-1;a_x=0;
    m_i=0xfffffff;i_x=0;
    ans=0;//多测清空 
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
      scanf("%d",&x);
      if(x>m_a){
        m_a=x;
        a_x=i;
      }
      if(x<m_i){
        m_i=x;
        i_x=i;
      }
    }
    if(i_x>a_x)swap(i_x,a_x);//若最小值在最大值后面，交换坐标 
    n_i=min(i_x,n-i_x+1);
    m_i=min(a_x,n-a_x+1);//找到两个坐标分别离两端的最短距离
    if(n_i<m_i){//摧毁离两端最近的石头 
      ans+=n_i;
      ans+=min(a_x-i_x,m_i);//摧毁新序列石头 
    }else{
      ans+=m_i;
      ans+=min(a_x-i_x,n_i);//摧毁新序列石头 
    }
    cout<<ans<<endl;//输出结果 
  }
  return 0; 
}