当前位置: 首页 > 工具软件 > Friends > 使用案例 >

小伙伴(friends)

侯善
2023-12-01

时间限制: 2 Sec 内存限制: 512 MB
题目描述
有n对小伙伴(每对2人),共2n个人坐成一圈。刚开始编号为i的人坐在第i个座位上。每次可以让相邻的两个人交换座位。问要让每一对小伙伴的座位都相邻至少需要多少次交换?
注意,由于所有人坐成一圈,所以第1个座位和第2n个座位也是相邻的。
输入
第一行一个正整数n,表示伙伴的对数。
接下来一行,包含2n个正整数,第i个正整数表示A_i,表示编号为i的人属于第A_i对小伙伴。1≤A_i≤n,且每一个数刚好出现2次。
输出
输出一行答案。
样例输入
3
1 2 3 1 3 2
样例输出
2
提示
【数据范围与约定】
对于10%的数据,n≤5
对于30%的数据,n≤20
对于60%的数据,n≤1000
对于100%的数据,n≤500000
题解
这道题有一个结论,先把每一对点之间的最短距离加起来,对于每两对点( X i X_i Xi Y i Y_i Yi),( X j X_j Xj Y j Y_j Yj),如果 X i ≤ X j ≤ Y i ≤ Y j X_i≤X_j≤Y_i≤Y_j XiXjYiYj,即两对点交叉时答案要 − 1 -1 1。减法时可以用树状数组维护。
证明不详,暂且不论。
确实有点难想,可能是我太菜了。
C o d e : Code: Code

#include<cstdio>  
#include<algorithm>  
using namespace std; 
const int N=1e7+7; 
int a[N],t[N],tree[N],n,b[N]; 
void add(int x,int y) 
{ 
    for(int i=x;i<=2*n;i+=i&(-i))tree[i]+=y;  
} 
int query(int x)  
{  
    int ans=0; 
    for(int i=x;i;i-=i&(-i))ans=ans+tree[i];  
    return ans;  
}  
int main()  
{  
    scanf("%d",&n);  
    for (int i=1;i<=2*n;i++)   
    {  
        scanf("%d",&a[i]); 
        if(t[a[i]])t[a[i]]=i-t[a[i]]-1;else t[a[i]]=i;  
    }  
    long long ans=0;  
    for(int i=1;i<=n;i++)ans+=min(t[i],2*n-t[i]-2);  
    for(int i=1;i<=2*n;i++) 
        if(b[a[i]])  
        {  
            add(b[a[i]],-1);  
            ans=ans-query(2*n)+query(b[a[i]]);  
        }else
        {  
            add(i,1);  
            b[a[i]]=i;  
        }  
    printf("%lld\n",ans);  
 }
 类似资料: