文章档案

用树状数组

# include <stdlib.h>
# include <stdio.h>

int c[10001];
  int lowbite(int x);
  int n;
int main ()
  {
  int sum(int i);
  void add(int i);
 
  long m,i,j,k,max=99999999,maxk;
  int a[10001];
  scanf("%d%d",&n,&k);
 for (i=1;i<=k;i++)
   {
    for (j=1;j<=n;j++) c[j]=0;
    m=0;
    for (j=1;j<=n;j++) scanf("%d",&a[j]);
    for (j=1;j<=n;j++)
      {
         m+=sum(a[j]-1);
         add(a[j]);
       }
    if (m<max) {max=m; maxk=i;}
   }
 printf("%d",maxk);
}

int sum(int i)
{
  int t=0;
 while (i>0)
 {
 t+=c[i];
 i-=lowbite(i);
 }
  return t;
 }
 
 void add(int i)
 {
 while (i<=n)
 {
 c[i]++;
 i+=lowbite(i);
 }
 }
 
int lowbite(int i)
{
    return i&(i^(i-1));
}