2237700_re.c

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# define MAX 70001
# define swap(a,b) a = a+b; b = a-b;a = a-b

int a[MAX], b[MAX], c[MAX];
int cnt;

void MergeSort(int l,int r)
{
      int mid,i,j,tmp;

      if (r>l+1)
      {
          mid = (l+r)/2;
          MergeSort(l,mid);
          MergeSort(mid,r);
          tmp = l;
          for (i=l,j=mid;i<mid&&j<r;)
          {
              if (a[i]>a[j])
              {
                  c[tmp++] = a[j++];
                  cnt+=mid-i;
              }
              else   c[tmp++] = a[i++];
          }
	if (j<r)
		for (;j<r;++j) c[tmp++] = a[j];
        else
		for (;i<mid;++i)   c[tmp++] = a[i];
	for (i = l ; i < r; ++i)
              a[i] = c[i];
      }
}

void input()
{
	int n, m, i;

	cnt = 0;
	scanf("%d%d",&n,&m);
	for(i = 0; i < n+m; i++)
		scanf("%d%d",&b[i],&a[i]);
	for(i = 0; i < n+m; i++)
		if(b[i]!=i+1)
		{
			swap(b[i],b[b[i]-1]);
			swap(a[i],a[b[i]-1]);
		}
	MergeSort(0,m+n);
	printf("%d\n\n",cnt);
}

int main()
{
	int i, t;

	scanf("%d",&t);
	for(i = 1; i <= t; i++)
		printf("Scenario #%d:\n",i),input();
	return 1;
}