UVa 11129 - An antiarithmetic permutation

【链接】

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=2070

【原题】

A permutation ofn+1is a bijective function of the initialn+1natural numbers: 0, 1, ...n. A permutationpis called antiarithmetic if there is no subsequence of it forming an arithmetic progression of length bigger than 2, i.e. there are no three indices 0≤i<j<k<nsuch that (p_i,p_j,p_k) forms an arithmetic progression.

For example, the sequence (2, 0, 1, 4, 3) is an antiarithmetic permutation of 5. The sequence (0, 5, 4, 3, 1, 2) is not an antiarithmetic permutation of 6 as its first, fifth and sixth term (0, 1, 2) form an arithmetic progression; and so do its second, fourth and fifth term (5, 3, 1).

Your task is to generate an antiarithmetic permutation ofn.

Each line of the input file contains a natural number 3≤n≤10000. The last line of input contains 0 marking the end of input. For eachnfrom input, produce one line of output containing an (any will do) antiarithmetic permutation ofnin the format shown below.

Sample input

3
5
6
0

Output for sample input

3: 0 2 1 
5: 2 0 1 4 3
6: 2 4 3 5 0 1

【题目大意】

输入N， 然后要由0，1，...N-1组成一个antiarithmetic序列， 这个序列不能有3个元素的等差子序列。

【分析与总结】

这题想了很久还是没思路。于是百度学习之。原来是运用了分治的办法，这一直是我比较弱的地方。

【代码】

/*
 * UVa: 11129 - An antiarithmetic permutation
 * 递归与分治
 * Time: 0.012s
 * Author: D_Double
 */

#include<cstdio>
int init[10003],tar[10003],T=10000;

void ST(int l,int h)
{
    int t=l;    
    if(l==h) return;
    for(int i=l;i<=h;i+=2)
        tar[t++]=init[i];
    for(int i=l+1;i<=h;i+=2)
        tar[t++]=init[i];
    for(int i=l;i<=h;i++)
        init[i]=tar[i]; 
    ST(l,(l+h)/2);
    ST((l+h)/2+1,h);
}

int main()
{   
    while(~scanf("%d",&T)&T){
        for(int i=0;i<T;i++)
           init[i]=i;
        ST(0,T-1);
        printf("%d: %d",T,tar[0]);
        for(int i=1;i<T;i++)
            printf(" %d",tar[i]);
        printf("\n");
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。
    
  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)