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 of n+1 is a bijective function of the initial n+1 natural numbers: 0, 1, ... n. A permutation p is 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 < n such that (pi, pj, pk) 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 of n.

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 each n from input, produce one line of output containing an (any will do) antiarithmetic permutation of n in 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个元素的等差子序列。

【分析与总结】

本栏目更多精彩内容：http://www.bianceng.cn/Programming/sjjg/

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

【代码】

/*
 * 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;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， input
， 分治法
， 分治递归
， 序列
， of
an
permutation、next permutation、next permutation函数、permutation test、permutation matrix，以便于您获取更多的相关知识。