给出一个的数列，将其重新排列，使得其等差子序列的数目最小。输出一种可能的排列后的数列。
题解
构造
那天和 EdwardFrog 讨论 bzoj2124 的构造时突然有的灵感，最后发现就是这道题...
通过构造可以使得不存在长度为3的等差子序列。
考虑：如果把所有奇数放到所有偶数的左面，那么就不会出现 “奇-偶-奇” 或 “偶-奇-偶” 的情况。
对于 “奇-奇-奇” 或 “偶-偶-偶” 的情况，将所有 $a_i$ 变为 $lfloorfrac{a_i}2 floor$ 不影响判断，因此将所有数除以2后重复这个过程即可。
由于一个数除以 $log n$ 次就会变成1，因此这个过程只需要进行 $log$ 次。
每一层都只会处理 $n$ 个数，时间复杂度 $O(nlog n)$ 。
#include <cstdio>
int a[510] , p[510] , t[510];
void solve(int l , int r , int x)
{
if(!x || l >= r) return;
int i , b = l , e = r;
for(i = l ; i <= r ; i ++ )
{
if(a[p[i]] & 1) t[b ++ ] = p[i];
else t[e -- ] = p[i];
}
for(i = l ; i <= r ; i ++ ) a[p[i]] >>= 1 , p[i] = t[i];
solve(l , e , x - 1) , solve(b , r , x - 1);
}
int main()
{
int n , i;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , p[i] = i;
solve(1 , n , 30);
for(i = 1 ; i <= n ; i ++ ) printf("%d " , p[i]);
return 0;
}