JOSWAP - Just One Swap

_H17_ · 2023-11-11 16:33:07 · 题解

题目分析

简单排列组合题。每个数可以换到除了他以外的所有位置。

我们设 a_i 是序列，mp_{a_i} 是 a_i 这个数出现的次数。

则每个数可以换到的位置有 n-mp_{a_i} 个。

我们需要求的 ans=(\sum_{i=1}^{n}n-mp_{a_i})\div 2。

然后你就 WA 了，如果有两个相同的数则他们互换可以得到原来的序列，需要特判！

代码实现

#include<bits/stdc++.h>
#define int long long //warning!
using namespace std;
int T,n,a[100001],ans;
bool f;
map<int,int>mp;//如题目分析
signed main(){
    for(cin>>T;T;--T){
        mp.clear();//清空
        cin>>n;
        ans=f=0;//重置
        for(int i=1;i<=n;i++){
            cin>>a[i];
            mp[a[i]]++;//增加
        }
        for(int i=1;i<=n;i++){
            if(mp[a[i]]>1)//特判！
                f=1;
            ans+=(n-mp[a[i]]);//求和
        }
        cout<<ans/2+f<<'\n';//多测勿忘换行
    }
    return 0；
}