Question

noip2013提高组day1第二题火柴排队

各路大侠能否解释一下noip2013提高组day1第二题火柴排队怎么做，附上C语言代码更好！万分感谢

Answer 1

首先 先了解排序不等式 可证明 只有第一列的第i大火柴和第二列的第i大火柴在一起的时候 才会符合要求

然后思路就很清晰了 你有两条路：
暴力之 先快排一个 然后用二分查找 调换 据说这么做就有七十分了真是丧心病狂.....如果你更蛋疼一点的话 可以试试看用 stl模版中的vector 没准能过ac.......没准

正解方法 先对两个排序 然后求逆序对.......这么说可能太笼统 举个例子
设 第一个序列是32145 第二个序列是52143
第二个序列排成第一个，那么相当于第二个序列中
5应当排第5个
2应当排第2个
1应当排第3个
4应当排第4个
3应当排第1个
于是就是求52341的逆序对，7个
逆序对和快排你一定都会打了 那就这样吧...
提供c++版本ac代码.........

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int d[1000001];
long long ans=0;
void stablesort(int *a,int l,int mid,int r)
{
int i=l,j=mid+1,k=l;
while (i<=mid && j<=r)
if (a[i]<=a[j]) d[k++]=a[i++];
else { d[k++]=a[j++]; ans+=mid+1-i;ans=ans%99999997;}
while (i<=mid)
d[k++]=a[i++];
while (j<=r)
d[k++]=a[j++];
for (int q=l;q<=r;q++) a[q]=d[q];
}

void merge(int *a,int l,int r)
{
if (l<r)
{
int mid=(l+r)/2;
merge(a,l,mid);
merge(a,mid+1,r);
stablesort(a,l,mid,r);
}
}

int n,c[1000001];
struct data{
int xx,yy;}a[1000001],b[1000001];

inline int cmp(const void *a,const void *b)
{
if ( (*(data *)a) .xx < (*(data *)b) . xx )
return 1;
else return -1;
}

int main()
{
scanf("%d",&n);
for (int q=0;q<n;q++) {scanf("%d",&a[q].xx);a[q].yy=q;}
for (int q=0;q<n;q++) {scanf("%d",&b[q].xx);b[q].yy=q;}
qsort(a,n,sizeof(data),cmp);
qsort(b,n,sizeof(data),cmp);

for (int q=0;q<n;q++)
c[b[q].yy]=a[q].yy;
merge(c,0,n-1);
printf("%d",ans);
//system("pause");
return 0;
}
（因为我只会c++）

Answer 2

首先贪心只有第一列的第i大火柴和第二列的第i大火柴在一起的时候才会符合要求。

那要如何求距离呢？？用逆序对。
用树状数组求出逆序对。
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<ctype.h>
#include<ctime>
#include<set>
#include<map>
#include<memory.h>
#include<cstring>
#include<iostream>
#include<fstream>
#include<vector>
#include<functional>
#include<queue>
#include<cassert>
#include<numeric>
#include<utility>
#include<deque>
#include<stack>
#include<bitset>
#include<list>
#include<iomanip>
#include<stdexcept>
#include<complex>
#include<iterator>
#define x first
#define y second
#define mp make_pair
using namespace std;
const int MAX=(1<<30);
pair<int,int>q[100001],q1[100001];
int pp[100001],s[100001];
int i,j,k,m,n;
const int mod=99999997;
int lowbit(int x)
{
return x&(-x);
}
int sum(int x)
{
int su=0;
while(x)
{
x-=lowbit(x);
su+=s[x],su%=mod;
}
return su;
}
int add(int x)
{
while(x<=n)
{
s[x]++,s[x]%=mod;
x+=lowbit(x);
}
return 0;
}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&k),
q[i]=mp(k,i);
for(i=1;i<=n;i++)
scanf("%d",&k),
q1[i]=mp(k,i);
sort(q+1,q+n+1);
sort(q1+1,q1+n+1);
for(i=1;i<=n;i++)
pp[q[i].y]=q1[i].y;
for(i=n;i>0;i--)
m+=sum(pp[i])%mod,m%=mod,add(pp[i]+1);
cout<<m<<endl;
return 0;
}