华中邀请赛现场赛F题 Seats

时间：2021-09-10 16:15:02

题目链接：http://acm.whu.edu.cn/land/problem/detail?problem_id=1552

解题报告：题目意思应该很清楚，就是有n个人，分别属于7个班级，然后他们坐成一排，现在要通过相邻的两个人做交换，使得所有同一个班的人都坐到一起，问这个交换的次数最少是多少？

比赛的时候第一个就是看这题，因为题意简单，但是看完了一点想法都没有，所以果断换了一题，看了题解才知道怎么做。

首先如果我们知道最后的排列是怎么样的，那么求一共要交换多少次就只要求初始状态跟最后的排列的逆序对的个数就可以了，然后因为班级最多只有7个，所以可以枚举7个班级的全排列，数据量也不大，一共才5040种情况。然后枚举出排列之后就是求有多少个逆序对了，对于这个有一个很巧妙的做法，利用到了这个题目中班级数少的特点，就是首先定义一个

f[i][j]二维数组，然后将初始的排列扫一遍，f[i][j] 的含义是所有排在   j 班同学前面的   i 班同学的人数，然后在求逆序对的时候只要班级的平方次计算就可以很快得出逆序对的个数，这个原理我想了好久，一开始不懂为什么这样可以，唉，还是太菜了啊。。。慢慢领悟吧

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #include<deque>

 #include<map>

 #include<queue>

 #include<cstdlib>

 using namespace std;

 typedef long long INT;

 const int maxn = ;

 INT f[][],ans,visit[],que[maxn+];

 INT judge(int *A)

 {

     INT sum = ;

     for(int i = ;i <= ;++i)

     for(int j = i+;j <= ;++j)

     sum += f[A[j]][A[i]];

     return sum;

 }

 void dfs(int* A,int deep)

 {

     if(deep > )

     {

         ans = min(ans,judge(A));

     }

     for(int i = ;i <= ;++i)

     if(!visit[i])

     {

         visit[i] = ;

         A[deep] = i;

         dfs(A,deep+);

         visit[i] = ;

     }

 }

 int main()

 {

     int n,A[];

     while(scanf("%d",&n)!=EOF)

     {

         for(int i = ;i < n;++i)

         scanf("%lld",&que[i]);

         INT e[];

         memset(e,,sizeof(e));

         memset(f,,sizeof(f));

         for(int i = ;i < n;++i)

         {

             for(int j = ;j <= ;++j)

             f[j][que[i]] += e[j];

             e[que[i]]++;

         }

         for(int i = ;i <= ;++i)

         f[i][i] = ;

         ans = 0x7ffffffffff;

         memset(visit,,sizeof(visit));

         dfs(A,);

         printf("%lld\n",ans);

     }

     return ;

 }

相关文章