//全排列问题的递归算法
void Perm(int list[],int k,int m)
{
    if(k==m)
    {
        for(int i=0; i<=m; i++)
            cout<<list[i]<<" ";
        cout<<endl;
    }
    else
        for(int j=k; j<=m; j++)
        {
            swap(list[k],list[j]);
            Perm(list,k+1,m);
            swap(list[k],list[j]);
        }
}
//正整数n的划分算法
int split(int n,int m)
{
    if(n==1||m==1)
        return 1;
    else if(n<m)
        return split(n,n);
    else if(n==m)
        return split(n,n-1)+1;
    else
        return split(n,m-1)+split(n-m,m);
}
//二分搜索算法
int BinarySearch(int a[],const int&x,int n)
{
    int left=0;
    int right=n-1;
    while(left<=right)
    {
        int middle=(left+right)/2;
        if(x==a[middle])
            return middle;
        if(x>a[middle])
            left=middle+1;
        else
            right=middle-1;
    }
    return -1;
}
//循环赛日程表算法
#define MAX 100
int a[MAX][MAX];
void Copy(int tox,int toy,int fromx,int fromy,int r)
{
    for(int i=0; i<r; i++)
        for(int j=0; j<r; j++)
            a[tox+i][toy+j]==a[fromx+i][fromy+j];
}
void Table(int k)
{
    int i,r;
    int m=1<<k;
    for(i=0; r<n; i++)
        a[0][i]=i+1;
    for(r=1; r<n; r<<=1)
    {
        Copy(r,r+i,0,i,r);
        Copy(r,i,0,r+i,r);
    }
}
//棋盘覆盖问题的分治算法
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
    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,dr+s-1; dc+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,dr+s,dc+s,s);
    }
}
//采用分治策略找出第k小的元素的算法
#define NUM 1001
int a[NUM];
int select(int left,int right,int k)
{
    if(left>=right)
        return a[left];
    int i=left;
    int j=right+1;
    int pivot=a[left];
    while(true)
    {
        do
        {
            i=i+1;
        }
        while(a[i]<pivot);
        do
        {
            j=j-1;
        }
        while(a[j]>pivot);
        if(i>=j)
            break;
        swap(a[i],a[j]);
    }
    if(j-left+1==k)
        return pivot;
    a[left]=a[j];
    a[j]=pivot;
    if(j-left+1<k)
        return select(j+1,right,k-j+left-1);
    else
        return select(left,j-1,k);
}
//输油管道问题
//采用排序算法计算中位数
int youguan1()
{
    int n;
    int x;
    int a[1000];
    cin>>n;
    for(int k=0;i<n;i++)
        cin>>x>>a[k];
    sort(a,a+n);
    int min=0;
    for(int i=0;i<n;i++)
        min+=(int)fabs(a[i]-a[n/2]);
    cout<<min<<endl;
}
//分治
int youguan2()
{
    int n;
    int x;
    int a[1000];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>x>>a[i];
    int y=select(0,n-1,n/2);
    int min=0;
    for(int i=0;i<n;i++)
        min+=(int)fabs(a[i]-y);
    cout<<min<<endl;
}
//计算半数集问题的递归算法
int comp(int n)
{
    int ans=1;
    if(n>1) for(int i=1;i<=n/2;i++)
        ans+=comp(i);
    a[n]=ans;
    return ans;
}
//计算半数集问题的递归算法---记忆式搜索
int a[1001];
int comp(int n)
{
    int ans=1;
    if(a[n]>0) return a[n];
    for(int i=1;i<=n/2;i++)
        ans+=comp(i);
    a[n]=ans;
    return ans;
}