P1092 - 【NOIP2013】火柴排队

Description

Input

共三行，第一行包含一个整数 n，表示每盒中火柴的数目。

第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。

第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

Output

输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

Sample Input

样例1：

4

2 3 1 4

3 2 1 4

样例2：

4

1 3 4 2

1 7 2 4

Sample Output

样例输出1：

1

样例输出2：

2

Hint

样例1说明

最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

样例2说明

最小距离是 10，最少需要交换 2 次，比如：交换第 1 列的中间 2 根火柴的位置，再交换第 2 列中后 2 根火柴的位置。

数据范围

对于 10%的数据， 1 ≤ n ≤ 10；

对于 30%的数据，1 ≤ n ≤ 100；

对于 60%的数据，1 ≤ n ≤ 1,000；

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ 2^31 − 1。

 

题解：

　　这个题目非常得绕，暴力又只有10分，真的很好奇60分算法是什么。

　　首先，他是想最小化sigam（ai-bi）^2,那么我们就最小化每个ai-bi，就可以了，怎么最小话呢？首先我们把两个序列排序，那么排名相对的两个数相减是最小的，贪心的证明都很难，大体手构几组数据才理解吧。

　　接下来的问题是怎么统计交换次数，我们看一下数据，显然是一个nlogn的算法，联赛里的log除了二分，可能就是排序和线段树，树状数组了吧，对于区间首先想到数据结构，那么交换次数显然是和逆序对数量相等的，因为每一对相邻的逆序对所需的交换次数就是1，当次数 用完时逆序对也就不存在了，所以就是逆序对的个数。那么怎么求呢？

　　考虑树状数组维护tr[x]，表示比x要小的数的个数，那么因为我们按顺序插入，前面一共有i-1个数，然后用树状数组求和比当先的数x大的个数sum,那么前面就有i-1-sum个比x大的数，x所做的贡献就是i-1-sum,然后把每个x所做的贡献加起来就是答案了。

 

代码：

#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define ll long long#define mod 99999997#define MAXN 100050using namespace std;struct h{ int xv,zhi;}a[MAXN];struct hh{ int xv,zhi;}b[MAXN];int r[MAXN],n;ll tr[MAXN],ans=0;bool cmp1(h x,h y){ return x.zhi
              
               >n; for(int i=1;i<=n;i++) scanf("%d",&a[i].zhi),a[i].xv=i; for(int i=1;i<=n;i++) scanf("%d",&b[i].zhi),b[i].xv=i; sort(a+1,a+n+1,cmp1); sort(b+1,b+n+1,cmp2); for(int i=1;i<=n;i++) r[a[i].xv]=b[i].xv; add(r[1]); for(int i=2;i<=n;i++){ ans+=i-1-sum(r[i]); add(r[i]); ans%=mod; } printf("%lld\n",ans); return 0;}