原题描述如下：

->原题链接<-

简短翻译一下：给定一个有限长度的数列其中，定义混乱度为下标的个数，满足；定义可执行的操作为交换任意数对和的值，试给定一种交换方法使得数列混乱度最低，并且给出最低混乱度。

评价：对称结构的考量

参考思路：

（1）所有奇数长度的数列都可以转换为偶数数列求解：

为什么？我用长度为5的数列作为一个例子说明！假设原始奇数长度数列，再构造，不难发现的混乱度是等于的。至此我们只需处理偶数长度的数列即可。

  1. 从对称中心出发，从内到外确定顺序：

为什么可行？？？考虑一下通用的情形：考虑，对于数列而言，到之间的数据是不会影响到左右两边的判断的。（为什么？因为混乱度的定义，混乱度只取决于相邻的元素，上述式子中的四个元素换来换去无非两种情况：和相邻or和相邻这两种情况罢了。所以无论到如何排布，外面的元素都可以调整以达到两种情况中的任意一种。所以内部的分布不应该影响到外部的判断！

基本策略：从对称中心出发，内向外单侧有相等即可交换

考虑一下通用的情形：考虑，基于我们上面的讨论：中间如何排布不应该影响外围元素排布的判断，所以我们其实只需要考虑这一部分即可。

先说我们的基本策略：

不难证明：如果，交换、总是更优的。这种情况下的交换至少一定不会增加混乱度！并且全局最优（穷举情况即可证明。

代码描述：

1
2
3
4
5
if(data[left+1]==data[left]||data[right]==data[right-1]){
    int tmp=data[left];
    data[left]=data[right];
    data[right]=tmp;
}

从对称中心从内向外确定交换元素后、交换元素重新计算混乱度即为最低的混乱度。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define MAX_NUM 100005

int count_vector(int* data,int len){
    int ans=0;
    for(int i=0;i<len-1;i++){
        if(data[i]==data[i+1]){
            ans++;
        }
    }
    return ans;

}

void print_arr(int* data,int len){
    for(int i=0;i<len;i++){
        printf("%d ",data[i]);
    }
    cout<<endl;
}


int main(){
    int data[MAX_NUM],data_len,test_num;  
    cin>>test_num;
    for(int i=0;i<test_num;i++){
        cin>>data_len;
        for(int j=0;j<data_len;j++){
            cin>>data[j];
        }
        
        if(data_len<=3){
            goto passed;
        }

        int left,right;
        if(data_len%2==0){
            left=data_len/2-1;
            right=data_len/2;
        }else{
            left=data_len/2;
            right=data_len/2;
        }
        left--;right++;
        while(left>=0){
            if(data[left+1]==data[left]||data[right]==data[right-1])
            {
                int tmp=data[left];
                data[left]=data[right];
                data[right]=tmp;
            }
            left--;right++;
        }

    passed:
        cout<<count_vector(data,data_len)<<endl;;

    }
    
    return 0;
}



鉴定为美美通过！睡大觉去咯！！！