POJ2182(Lost Cows)

最近在写遗传算法求TSP时看到了grefenstette编码，于是想起了这个题目，这题我原来是用线段树写的C语言提交的，用时157ms，刚用树状数组+二分写用C++提交只跑了47ms，感觉快了不少。

这题数学模型是：现有一个1到n的一个被打乱的排列，告诉你每个数的左边有多少个数比它小，显然第一个数左边没有比它小的数，求每个位置上的数。

grefenstette编码差不多，只是把左边改成了右边再加1，例如：8 6 7 5 3 4 1 2编码后是：8 6 6 5 3 3 1 1

#include <stdio.h>
#include <string.h>
#define N 8010
int a[N],c[N],f[N],n;
void update(int k)
{
  for(;k<=n;k+=(k&(-k))) f[k]++;
}
int getsum(int k)
{
  int sum=0;
  for(;k>0;k-=(k&(-k)))  sum+=f[k];
  return sum;
}
int bs(int k)
{
  int min=0,max=n,mid;
  while(min+1!=max)
  {
    mid=(min+max)>>1;
    if(mid-1-getsum(mid)<a[k])  min=mid;
    else  max=mid;
  }
  return max;
}
int main()
{
  while(~scanf("%d",&n))
  {
    a[1]=0;
    for(int i=2;i<=n;i++) scanf("%d",&a[i]);
    memset(f,0,sizeof(f));
    for(int i=n;i>0;i--)
    {
      c[i]=bs(i);
      update(c[i]);
    }
    for(int i=1;i<=n;i++) printf("%d\n",c[i]);
  }
  return 0;
}

这题太经典了，又用线段树（堆实现的）写了一遍，时间还是47ms。感觉这个思路更清晰，更巧妙。 

#include <stdio.h>
#define N 8002
int n,D;
int x[N],id[N];
int sum[4*N];
void init()
{
  int i;
  for(D=1;D<n+2;D<<=1);
  for(i=1;i<=n;i++) sum[i+D]=1;
  for(i=D-1;i;i--)  sum[i]=sum[i<<1]+sum[i<<1|1];
}
void update(int k)
{
  k+=D;
  sum[k]=0;
  for(;k^1;k>>=1) sum[k>>1]=sum[k]+sum[k^1];
}
int query(int k)
{
  int i;
  for(i=1;i<D;)
  {
    if(sum[i<<1]>=k)  i<<=1;
    else  k-=sum[i<<1],i=i<<1|1;
  }
  return i-D;
}
int main()
{
  int i;
  while(~scanf("%d",&n))
  {
    x[1]=0;
    for(i=2;i<=n;i++) scanf("%d",&x[i]);
    init();
    for(i=n;i;i--)
    {
      id[i]=query(x[i]+1);
      update(id[i]);
    }
    for(i=1;i<=n;i++) printf("%d\n",id[i]);
  }
  return 0;
}