UVa 11129 An antiarithmetic permutation (构造题&想法题&分治)

11129 - An antiarithmetic permutation

Time limit: 3.000 seconds

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 permutationp 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 (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 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

UVa 10730 的逆问题。

思路：

先把序列分成奇偶序列（把奇在位置上的数分成一组，在偶位置上的数分成一组），这两个序列之间不会形成等差序列。同样再在奇偶序列中再这样分，这样分就能保证不会出现等差序列。

完整代码：

/*0.012s*/

#include<cstdio>

int n, num[10010], tempa[5010], tempb[5010];

void divide(int l, int r)
{
	if (l == r) return;
	int a = 0, b = 0, aa = 0, bb = 0, i;
	for (i = l; i <= r; i += 2)     tempa[a++] = num[i];
	for (i = l + 1; i <= r; i += 2) tempb[b++] = num[i];
	for (i = l; i < l + a; ++i)     num[i] = tempa[aa++];
	for (; i <= r; ++i)             num[i] = tempb[bb++];
	divide(l, l + a - 1); divide(l + a, r);
}

int main(void)
{
	while (scanf("%d", &n), n)
	{
		for (int i = 0; i < n; ++i)
			num[i] = i;
		divide(0, n - 1);
		printf("%d:", n);
		for (int i = 0; i < n; ++i)
			printf(" %d", num[i]);
		putchar('\n');
	}
	return 0;
}