1655: 手套
时间限制: 1 Sec内存限制: 128 MB
提交: 25解决: 13
[提交][状态][讨论版]
题目描述
你现在有N对手套，但是你不小心把它们弄乱了，需要把它们整理一下。N对手套被一字排开，每只手套都有一个颜色，被记为0~N-1，你打算通过交换把每对手套都排在一起。由于手套比较多，你每次只能交换相邻两个手套。请你计算最少要交换几次才能把手套排整齐。
输入
输入第一行一个N，表示手套对数。
第二行有2N个整数，描述了手套的颜色。每个数都在0~N-1之间，且每个数字都会出现恰好两次。
输出
一行，包含一个数，表示最少交换次数。
样例输入
2
0 1 0 1
样例输出
1
提示
30%的数据N≤9；

60%的数据N≤1000；

100%的数据N≤200,000。

解题思路
首先看到题目想到暴力模拟贪心求解O(n^2)算法对于数据一定超时；于是进行优化，大胆假设对手套进行重新编号就发现交换次数竟然和逆序对的模板的规律类似，于是发现可以用逆序对求解； 但是还是要求证的（不然会想班长大人一样爆零）
命题：上述操作的次数等于重新编号后数组的逆序对个数
引理：先对哪对手套进行操作并不影响答案（口糊见上）
证明：我们先把剩余数组中重新编号最小那对手套换完。所以我们只需要交换那后半只手套到第二的位子就可以了 要交换的次数是原序列中编号这对手套的 得证啦！
卡点
1.注意变量名不要冲突；
2.一般求解逆序对的过程中要把最后的答案改为long long否则会炸点；
3.数组开两倍较好；
代码：
#include<cstdio>
using namespace std;
int a[400005],b[400005],t[400005];
int n,q;long long ans;
void merge(int p,int r){
    if(p>=r)return;
    int m=(p+r)>>1;
    merge(p,m);merge(m+1,r);
    int i=p,j=m+1,k=p;
    while(i<=m&&j<=r)
        if(a[i]<=a[j])t[k++]=a[i++];
        else{
            t[k++]=a[j++];
            ans+=m-i+1;
        }
    while(i<=m)t[k++]=a[i++];
    while(j<=r)t[k++]=a[j++];
    for(int x=p;x<=r;x++)a[x]=t[x];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n*2;i++){
        scanf("%d",&a[i]);
        if(b[a[i]]==0)b[a[i]]=++q;
    }
    for(int i=1;i<=n*2;i++)
        a[i]=b[a[i]];
    merge(1,2*n);
    printf("%lld",ans);
    return 0;
}


心得
1.要注意题目与模板的转换，观察出两者的联系而不是一味地模拟以寻求正解否则会适得其反；
2.ans的值一定要想清楚了再做，千万不要越界；
3.逆序对的应用与分治算法有关，要注意分治的递归树一定画对，千万不要出错。