欧布美丽圆环

问题描述

红凯小蓝得到了一个O-50的欧布圆环，圆环上挂着 N 个奥特曼卡数字 A0,A1,A2,…,AN−1A0​,A1​,A2​,…,AN−1​。

为了使圆环变成一个美丽的圆环，需要满足以下条件：

对于第 ii 个数字 AiAi​，它的相邻数字为 A(i−1+N) mod NA(i−1+N)modN​ 和 A(i+1) mod NA(i+1)modN​。其中，至少有一个相邻数字大于等于 AiAi​，另一个相邻数字小于等于 AiAi​。
现在，小蓝想要让圆环变得足够美丽。他可以进行任意次以下操作：

将圆环上的任意数字更改为任意整数。
交换圆环上任意两个数字的位置。
请问，小蓝最少需要进行多少次操作 才能使圆环变成一个美丽的圆环？

输入格式

第一行包含一个整数 T(1≤T≤1000)T(1≤T≤1000)，表示测试数据的组数。

对于每组测试数据：

第一行输入一个 N(2≤N≤100)N(2≤N≤100)，表示圆环上数字的个数。
第二行输入 NN 个整数 A0,A1,A2,⋯ ,AN−1A0​,A1​,A2​,⋯,AN−1​，表示圆环上的数组 A(1≤Ai≤N)A(1≤Ai​≤N)。
输出格式
对于每组测试用例输出一行一个整数表示答案。

正解
由于不限制操作2的次数，所以排序后中间一定是满足条件的，所以我们只需要考虑首和尾的情况

由于数据范围N是从2开始的，并且这种情况，第一个元素与第二个元素，倒数第一个和倒数第二个元素是同一个，我们可以特殊考虑这种情况 如果首尾相等，那么操作次数为0，否则就为1

对于其他情况，我们要考虑首和尾，统计不相同的次数，特别注意，如果第二个元素和第三个元素相同或者最后第二个和最后第三个相同，我们只需要改变第一个元素，并且使用操作2交换位置即可

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N];

int main()
{
  int t;
  cin>>t;
  while(t--)
  {
    cin>>n;
    for(int i = 1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    int ans = 0;
    if(n == 2)
    {
      if(a[1] == a[2])ans = 0;
      else ans = 1;
    }  
    else
    {
      if(a[1] != a[2])ans++;
      if(a[n-1] != a[n])ans++;
      if(ans == 2)
      {
        if(a[2] == a[3] || a[n-1] == a[n-2])ans = 1;
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}