题目：11129 - An antiarithmetic permutation
题目大意：求n的反算术级数。就是排序0 。。n - 1 要求不存在长度大于2的序列。例如：5的序列排列后(0, 5, 4, 3, 1, 2) ，但是（0，1，2）是一个等差序列，同样的还有（5，4，3）， （5，3，1）...
解题思路：这题需要找到排列的策略：将整个序列分成差不多等长的两个部分，使得左右两部分各自成为等差数列，这样左边的数和右边的数组合就一定不会出现等差数列。然后把这个作为子问题，递归求解。递归到左右部分小于等于2可以了，因为它要求不出现长度为3以上的等差数列。
代码：
#include <stdio.h> const int N = 10005; int n; //k等差 ， t用来存放排列后的序列，
void solve (int l, int r, int *t, int k) {
if (r + 1 - l <= 2) //长度不大于2就可以返回了
return;
int m = l + (r - l) / 2;
int temp = t[l + 1];
for (int i = l, j = t[l]; i <= m; i++, j += k)
t[i] = j;
for (int i = m + 1, j = temp; i <= r; i++, j += k)
t[i] = j;
solve (l, m, t, k * 2);
solve (m + 1, r, t, k * 2);
}
int main () {
while (scanf ("%d", &n), n) {
int t[N];
for (int i = 0; i < n; i++)
t[i] = i;
solve(0, n - 1, t, 2);
printf ("%d:", n);
for (int i = 0; i < n; i++)
printf (" %d", t[i]);
printf ("\n");
}
return 0;
}uva:11129 - An antiarithmetic permutation（分治法）,布布扣,bubuko.com
uva:11129 - An antiarithmetic permutation（分治法）
原文：http://blog.csdn.net/u012997373/article/details/37089537