1276 士兵队列训练问题.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//采用移动 来减少查找第2或3个时的时间消耗
//而且移动后，数据从 n -> n/2 -> n/3 -> n/6 -> n/9 ....
//如果用朴素的比较 ，按照第 i位喊 k来标识，将TLE，此时移动数据才不会超时 
#include <cstdio>
#include <string>
using namespace std;
int q[5010];
int inc[2]={2,3};

int main()
{
	int i,j,n,k,t;
	
	scanf("%d",&t);
	while( t-- )
	{
		scanf("%d",&n);	
		for(i=0;i<=n;i++)
			q[i]=i;
		
		for(i=2; n>3 ;i++)
			if(inc[i%2]==2)
			{
				for(j=3,k=2; j<=n ;j+=2)
					q[k++]=q[j];
				n-=n/2;
			}
			else
			{
				for(j=4,k=3; j<=n ;j+=3 )
				{
					q[k++]=q[j];
					if(j+1<=n)
						q[k++]=q[j+1];
				}
				n-=n/3;
			}
				
		if(n==3)
			printf("1 %d %d\n",q[2],q[3]);
		else
		{
			printf("1");
			for(i=2;i<=n;i++)
				printf(" %d",q[i]);
			printf("\n");
		}
	}
	return 0;
}