JZ高中OJ 1386. 排序

Time Limits: 1000 ms  Memory Limits: 65536 KB  Detailed Limits  

Description

　　你收到一项对数组进行排序的任务，数组中是1到N个一个排列。你突然想出以下一种特别的排序方法，分为以下N个阶段：
　　•阶段1，把数字1通过每次交换相邻两个数移到位置1；
　　•阶段2，用同样的方法把N移到位置N；
　　•阶段3，把数字2移到位置2处；
　　•阶段4，把数字N-1移到位置N-1处；
　　•依此类推。
　　换句话说，如果当前阶段为奇数，则把最小的未操作的数移到正确位置上，如果阶段为偶数，则把最大的未操作的数移到正确位置上。
　　写一个程序，给出初始的排列情况，计算每一阶段交换的次数。

 

Input

　　第一行包含一个整数N(1<=N<=100000)，表示数组中元素的个数。
　　接下来N行每行一个整数描述初始的排列情况。

Output

　　输出每一阶段的交换次数。

 

Sample Input

输入1：
3
2
1
3


输入2：
5
5
4
3
2
1

输出3：
7
5
4
3
7
1
2
6

Sample Output

输出1：
1
0
0

输出2：
4
3
2
1
0

输出3：
4
2
3
0
2
1
0

 

Data Constraint

 

 

Hint

【数据范围】
　　70%的数据N<=100

#include <bits/stdc++.h>
#define MAX 100000
int n;
int numbers[MAX+1];
int position[MAX+1];
struct fenwick {
   int a[MAX+1];
   fenwick() {
      memset( a, 0, sizeof a );
   }
   int query( int X ) {
      int ret = 0;
      for( int x = X; x > 0; x -= x&-x )
         ret += a[x];
      return ret;
   }
   int sum( int lo, int hi ) {
      return query( hi ) - query( lo-1 );
   }
   void add( int X, int val ) {
      for( int x = X; x <= n; x += x&-x )
         a[x] += val;
   }
} alive;
int main( void ) {
   scanf( "%d", &n );
   for( int i = 1; i <= n; ++i ) {
      scanf( "%d", &numbers[i] );
      position[numbers[i]] = i;
      alive.add( i, 1 );
    }
   int mini = 1, maxi = n;

   for( int i = 1; i <= n; ++i ) {
      if( i%2 == 1 ) {
         alive.add( position[mini], -1 );
         printf( "%d
", alive.sum( 1, position[mini] ) );
         ++mini;
      } else {
         alive.add( position[maxi], -1 );
         printf( "%d
", alive.sum( position[maxi], n ) );
         --maxi;
      }
   }
   return 0;
}