uva - 11129 - An antiarithmetic permutation（分治）

题意：给定一个n，代表从0到n-1，n个数的排列，如果这个排列中找不到任何一个长度大于2的等差序列，称这个数列为等差级数。输出任意一个等差级数。

方法：

1、举例n=6，0，1，2，3，4，5。分成1，3，5；0，2，4，再连成1，3，5，0，2，4。这样得到的数列前边和后边不会形成等差数列。那么我们一直这样做，类似二分法，知道让子序列<=2时候退出。这时候的序列就满足题意。实现的时候要两个数组互相拷贝。

#include <iostream>      
#include <iomanip>      
#include <string>      
#include <cstring>      
#include <cstdio>      
#include <queue>      
#include <stack>      
#include <algorithm>      
#include <cmath>      
#include <ctime>  
  
using namespace std;

int n = 0, flag = 0;;
const int maxn = 10000+10;
int num[maxn], cop[maxn];

void Makelist()
{
	int i = 0;
	for (i = 0; i < maxn; i++)
		cop[i] = i;
	return;
}

void Input()
{
	int i = 0;
	cout << n << ":";
	for (i = 0; i < n; i++)
		cout << " " << num[i];
	cout << endl;
}

void Solve(int start, int end)
{
	int i = start, j = start;
	for (i = 0; i < n; i++)
		num[i] = cop[i];
	if (end - start <= 2)
		return;
	for (i = start; i < end; i +=2)
		cop[j++] = num[i];
	for (i = start+1; i < end; i += 2)
		cop[j++] = num[i];
	Solve(start, (start+end+1)/2);
	Solve((start+end+1)/2, end);
}

int main()
{
	while (cin >> n && n)
	{
		Makelist();
		memset(num, 0, sizeof(cop));
		Solve(0, n);
		Input();
	}
	return 0;
}

（1）注意每次都要重新打表。

（2）注意后半部分处理时候j应该从start开始，自己纸上演示下最好。

2、TLE代码。（感觉会TLE因为n最大到10000，但是不死心敲了一下果然）

#include <iostream>      
#include <iomanip>      
#include <string>      
#include <cstring>      
#include <cstdio>      
#include <queue>      
#include <stack>      
#include <algorithm>      
#include <cmath>      
#include <ctime>  
  
using namespace std;

int n = 0, flag = 0;;
const int maxn = 10000;
int num[maxn], vis[maxn], ans[maxn];

void Makelist()
{
	int i = 0;
	for (i = 0; i < maxn; i++)
		num[i] = i;
	return;
}

void Input()
{
	int i = 0;
	cout << n << ":";
	for (i = 0; i < n; i++)
		cout << ans[i] << " ";
	cout << endl;
}

int Handle()
{
	int i = 0;
	for (i = 1; i < n; i++)
	{
		if ((ans[i] - ans[i-1]) == (ans[i+1] - ans[i]))
			return 0;
	}
	return 1;
}

void DFS(int cur)
{
	int i = 0, j = 0;
	if (cur == n)
	{
		if (Handle())
		{
			flag = 1, Input();
		}
		else
			return;
	}
	else
	{
		if (flag)
			return;
		for(i = 0; i < n; i++)
		{
			if (!vis[i])
			{
				vis[i] = 1, ans[cur] = num[i];
				DFS(cur+1);
				vis[i] = 0;
			}
		}
	}
}

int main()
{
	Makelist();
	while (cin >> n && n)
	{
		flag = 0;
		DFS(0);
		memset(vis, 0, sizeof(vis));
		memset(ans, 0, sizeof(ans));
	}
	return 0;
}

uva - 11129 - An antiarithmetic permutation（分治）,布布扣,bubuko.com

uva - 11129 - An antiarithmetic permutation（分治）

原文：http://blog.csdn.net/u013545222/article/details/22660267