分治法进阶练习

第1关：线性时间选择问题

#include <iostream>
using namespace std;
 
void Swap(int &a,int &b)
{//交换函数
	 /*********begin************/
    int c;
	c = a;
	a = b;
	b = c;
 
    /*********end************/
}
 
 
int Partition(int a[],int p,int r,int x)
{//以x为基准划分函数
	 /*********begin************/
    int i = p,j = r;
 
    while(i <= r && j >= p)
    {
        while(a[i] < x) i ++ ;
        while(a[j] > x) j -- ;
        if(i >= j) break;
        else
        {
            Swap(a[i],a[j]);
            i ++ ,j -- ;
        }
    }
 
    return j;
    /*********end************/
}
 
void BubbleSort(int a[],int p,int r)
{//冒泡排序
    
    /*********begin************/
    for(int i = p;i < r;i ++ )
    {
        int k = i;
        for(int j = i + 1;j <= r;j ++ )
            if(a[j] < a[k])
                k = j;
        
        Swap(a[i],a[k]);
    }
    /*********end************/
}
int Select(int a[],int p,int r,int k)
{
    /*********begin************/
    if(r - p < 75) 
    {
        BubbleSort(a,p,r);
        return a[p + k - 1]; 
    }
 
    for (int i = 0; i <= (r - p - 4) / 5; i++)
    {
        BubbleSort(a,p + 5 * i, p + 5 * i + 4);
        int temp = a[p + 5 * i + 2];
        a[p + 5 * i + 2] = a[p + i];
        a[p + i] = temp;
    }
 
    int x = Select(a,p,p + (r - p - 4)/5,(r - p - 4)/10 + 1);
    int u = Partition(a,p,r,x);
    int v = u - p + 1;
    if(k == v) return a[u];
    else if(k < v) return Select(a,p,u,k);
    else return Select(a,u + 1,r,k - v);
 
    /*********end************/
}

第2关：众数问题

int getMode(int a[],int p,int r,int &Cnt)
{
    int *num = new int [100];
 
    int maxv = 0;
    for(int i = p;i <= r;i ++ )
    {
        num[a[i]] ++ ;
        if(a[i] > maxv)
            maxv = a[i];
    }
        
    int idx = 0,t = 0;
    for(int i = 0;i <= maxv;i ++ )
        if(num[i] > t)
        {
            idx = i;
            t = num[i];
        }
    
    Cnt = t;
 
    return idx;
}

第3关：求逆序对数

//归并排序及求逆序对
#include<iostream>
using namespace std;
#define N 1000005
int a[N], b[N];//b为辅助数组
long long cnt;
void merge_sort(int l, int r)
{
	// 如果整个区间中元素个数大于1，则继续分割
	if (r - l > 0)
	{
		// 1、尽量划分为数量相等的2个子序列，并排序
		int mid = (l + r) / 2;
		merge_sort(l, mid);
		merge_sort(mid + 1, r);
 
		// 2、将2个有序的序列合并成一个有序序列，在左右有序的子数组合并的同时，统计逆序对数
		/*********Begin***********/
        int i = l,j = mid + 1,k = l;
        while(i <= mid && j <= r)
        {
            if(a[i] <= a[j]) b[k ++ ] = a[i ++ ];
            else b[k ++ ] = a[j ++ ],cnt += mid - i + 1; 
        }
 
        while(i <= mid) b[k ++ ] = a[i ++ ];
        while(j <= r) b[k ++ ] = a[j ++ ];
        
       /*********End***********/
		// 3、将辅助数组b中排好序的元素复制到a中
		for (i = l; i <= r; i++)
			a[i] = b[i];
	}
}
int main()
{
	int n;
	while (cin >> n)
	{
		for (int i = 1; i <= n; i++)
			cin >> a[i];
		cnt = 0;
		merge_sort(1, n);
 
		cout << cnt << endl;
	}
	return 0;
}

第4关：棋盘覆盖问题

 #include<iostream>
#include<iomanip>
# define SIZE 32
using namespace std;
 
int tile = 0;
int Board[SIZE][SIZE];
//棋盘以(tr,tc)为左上角，以size为边长，特殊方格位置在(dr,dc)，ChessBoard函数用分治法
//完成它四个子棋盘覆盖
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
/************Begin**************/
  if (size == 1) return ;
 
  int t = tile ++;
  int s = size / 2;
 
  if (dr < tr + s && dc < tc + s)
    ChessBoard(tr,tc,dr,dc,s);
  else 
  {
    Board[tr + s - 1][tc + s - 1] = t;
    ChessBoard(tr,tc,tr + s - 1,tc + s - 1,s);
  }
 
  if (dr < tr + s && dc >= tc + s)
    ChessBoard(tr,tc + s,dr,dc,s);
  else 
  {
    Board[tr + s - 1][tc + s] = t;
    ChessBoard(tr,tc + s,tr + s - 1,tc + s,s);
  }
 
  if (dr >= tr + s && dc < tc + s)
    ChessBoard(tr + s,tc,dr,dc,s);
  else 
  {
    Board[tr + s][tc + s - 1] = t;
    ChessBoard(tr + s,tc,tr + s,tc + s - 1,s);
  }
    
  if (dr >= tr + s && dc >= tc + s)
    ChessBoard(tr + s,tc + s,dr,dc,s);
  else 
  {
    Board[tr + s][tc + s] = t;
    ChessBoard(tr + s,tc + s,tr + s,tc + s,s);
  }
/************End**************/
 
}
int main()
{
    /************Begin**************/
    int size,dr,dc;
    cin >> size >> dr >> dc;
 
    ChessBoard(0,0,dr,dc,size);
    Board[dr][dc] = -1;
    /************End**************/
    for (int i = 0; i < size; i++) 
    {
		  for (int j = 0; j < size; j++)
			  cout << setw(4) << Board[i][j];
 
		  cout << endl;
    }
 
  return 0;
}