[UVA][分治] 11129 - An antiarithmetic permutation
Problem A: An antiarithmetic permutation
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
W. Guzicki, adapted by P. Rudnicki
首先題目要求找到一組排列，排列中的任何子序列不會等差級數。
這題的思路相當巧秒，首先會發現 {偶數, 奇數, 奇數}, {偶數, 偶數, 奇數} 沒辦法構成等差。
接著我們將原本的數列{1,2,3, ... , n}畫分成 {偶數}{奇數}，
要不在第一個內部抓兩個，然後抓後面的那的一個，要不前面抓一個後面抓兩個，這樣全都沒辦法湊成等差。
但是 {偶數} 在這裡面抓三個就會有問題，因此我們繼續畫分這個{偶數}，按照原本的思路，同理 {奇數}。
之所以可以這麼作，是因為等差同是二個倍數的話，等價可以將其全部除二去看。
#include <stdio.h>
using namespace std;
int T[10005], A[10005];
void DC(int l, int r) {
if(l >= r) return ;
int i, j, k;
for(i = l; i <= r; i++)
T[i] = A[i];
for(i = l, j = l; i <= r; i += 2)
A[j++] = T[i];
k = j;
for(i = l+1; i <= r; i += 2)
A[j++] = T[i];
DC(l, k-1);
DC(k, r);
}
int main() {
int n, i;
while(scanf("%d", &n) == 1 && n) {
for(i = 0; i < n; i++)
A[i] = i;
DC(0, n-1);
printf("%d:", i);
for(i = 0; i < n; i++)
printf(" %d", A[i]);
puts("");
}
return 0;
}