先看题目:
【思路详解】:
首先,我们看到这一题时的第一反应一定是打一个朴素算法(懒人暴力),这一题的正解碰巧就是模拟+剪枝
我们先按照题意来写出一个模拟,分为每个阶段now,now的初始值为2(阶段指的是要把这个序列分成几组),每一个阶段都将这个序列分为now组,然后将每一组的第一个元素放到这一组的尾部。时间复杂度大概为O(n^2),非常好打,这样打60分肯定是没问题的,但是100分是怎么拿的呢,如果这一题想要AC就一定要做出一些剪枝才行,我们看这一题的空间:524288 KB,非常的大,所以我们本着以空间换取时间的想法进行优化。
我们发现,纯暴力慢的原因主要是在把每一组的开头元素移到组尾后这个组的其他元素会往前移,这时我们用的是for循环一个一个换位置,这当然很慢,所以我们着手在这方面进行优化。可以发现每一个组的元素都要放到队尾,那我们把这一组的第一个元素放到下一组的第一个位置,然后下一组第一个元素放到下下一组的第一位,这样我们就可以不用在移动元素了,只需要在最后一组时多开一个空间将最后一组第一个元素放进去就好了,这样我们一次分组多开一个空间,我们一共需要分组n-1次,我们就开两倍空间不就好了,这样就可以将时间复杂度降到O(nlogn)就可以AC了。
下面上代码:
#include<iostream> #include<cstdio> using namespace std; int n,now,lo,hi,a[2000010]={0},bot; //2倍空间 void change(){ //进行分组 bot=a[lo]; //暂时存放 for(int i=lo;i<=hi;i+=now){ if(i+now>hi){ a[++hi]=bot; lo++; break; } swap(bot,a[i+now]); //交换 } } int main(){ cin>>n; now=2; lo=1,hi=n;//用lo,hi标记现在的开头和结尾元素位置 for(int i=1;i<=n;i++) a[i]=i; while(now<=n){ change(); now++; } for(int i=lo;i<=hi;i++) cout<<a[i]<<" "; }
总结:这是一道大水题,细心就能AC(当然还得有脑子,所以我WA了40分)。