前言 这里是蒟蒻TIMEpings，这是我第一次真正动手写题解 (虽然之前有想过很多次) ，有误之处请各位大佬多多指出(=・ω・=)！

快速导航ε=ε=(ノ≧∇≦ノ

思路1-完全模拟(TLE警告)全局变量们main()doworm()bool cmp(const int &a,const int &b)cut(int topworm)grow() print_answer() 思路2-各种优化(AC)各种分析(´･_･`)主要优化思路从m遍sort到1遍sort从"蚯蚓"遍grow()到简单运算 数组模拟队列,还能解决长长问题！数组模拟队列的模板(模板代码写的不是很科学233) 代码部分全局变量们main()doworm()get_worm()cut() doline2() 快乐AC 原题太长了…在本题解内就不贴出原题了，不过看题解的人都应该有原题吧！ 题目传送门(LOJ)

思路1-完全模拟(TLE警告)

当蒟蒻走投无路时，这种解法是骗分的好助手

全局变量们

#define MAXN 7100000+7 //n+m的最大值,我把所有的蚯蚓都放里面了 int worm[MAXN]; int n,m,q,u,v,t; double p; int now_worm_cnt; //当前蚯蚓计数 int spc; //读秒,第一行的输出所需 int edT; //要求的[输出m秒后第n*t名的蚯蚓长度]的次数

main()

scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t); p = u*1.0/v; //有理数警告 now_worm_cnt=n; //现在有n条蚯蚓(废话) int ai; for(int i=1;i<=n;i++) { scanf("%d",&ai); worm[i]=ai; } edT = (n+m)/t; for(int i=1;i<=m;i++) doworm(); print_answer();

先输入6个参数，提前把p算出来(这样可能会影响精度,不推荐)，向worm里存每个蚯蚓,edT算出来也算是半个暴力优化，在print_answer()里面会体现。 时间复杂度的主要承担者之一doworm()需要循环做m次。

doworm()

“模拟的大框架”

spc++; //第一行输出记步 sort(worm+1,worm+1+now_worm_cnt,cmp); //降序自动快排咯 int topworm = worm[1]; //刀砍出头虫 if(spc==t) //步输出周期已到 { printf("%d ",topworm); //出头虫上榜 spc=0; //读秒归零 } cut(topworm); //砍 grow(); //长 now_worm_cnt++; //蚯蚓数量+1 return;

bool cmp(const int &a,const int &b)

return a>b;

定义的新运算规则就只有这一行，为的是让sort函数进行降序排序。不太了解的大佬可以百度一下ovo。 spc是一个独立的周期记步器，每进行一次doworm()读一步，当读到t步的时候，按题目要求输出当前最长的蚯蚓，并归零记步器。(AC题解对这个概念进行了优化) 这个完全模拟会TLE的其中一个原因，就是因为每进行一步模拟都会进行一次STL的sort快排，导致当m大的时候，特别是还有q的存在(蚯蚓长长)时，没法在1s内完成(´；ω；`)¹。

cut(int topworm)

int len1 = floor(p*topworm); //floor(p*x) int len2 = topworm-len1; //x-floor(p*x) worm[1]=len1; //第一个半只放前面 worm[now_worm_cnt+1]=len2; //第二个半只放后面

grow()

“时间复杂度的第二承担者”

if(q==0) return; //对于q=0的数据的特殊优化 for(int i=2;i<=now_worm_cnt;i++) { worm[i]+=q; //每条原来的蚯蚓长度+q }

首先q=0的特殊数据既然给到我们，那么就可以尽可能的去利用它。少一遍循环多一点希望。 for循环的起点和终点要结合cut()函数一起看，因为刚砍半的蚯蚓是不会立刻长长的，所以就忽略这两条。

(回到doworm())每切一次，蚯蚓的数量应该++。

print_answer()

(对第二行输出的处理)

printf("\n"); //空行 sort(worm+1,worm+1+now_worm_cnt,cmp); //神秘人物来后的排序 for(int i=1;i<=edT;i++) printf("%d ",worm[i*t]); //输出第i*t位的虫

空行这个坑千万不要掉进去了 最后一次砍蚯蚓的时候没有进行sort，于是此处再进行一次。 edT在这里发挥了作用，算个暴力优化，少一点循环也多一点希望。

思路1的时间复杂度能骗个30多分了(´･_･`)。

思路2-各种优化(AC)

各种分析(´･_･`)

发现自己没AC之后，第一时间肯定是上网查题解啦！ 搜到的各大佬的写法，很多都提到了队列(还是3个队列)，基本思路也差不多相似，不过也发现了我想的数组写法。自己在琢磨透之后，就想着能不能把更好看的数组模拟写法再写的好理解一点

主要优化思路

从m遍sort到1遍sort

思考： 1.第一遍sort之后，所有的蚯蚓应该是降序排列的。 2.一个有序队列中所有蚯蚓的生长，不会影响它们的有序性。 3.如果把放在首位的蚯蚓出队，不会影响其它蚯蚓的有序性。 4.将出队的蚯蚓按照要求砍半后，分别放入另外两个队列，如果此时要求较长的半条永远放入队列2，较短的半条永远放在队列3，由于先放入某队列的半条(在不考虑生长的情况下)长度永远大于等于后放入的半条长度，故这两个队列同样也是降序的。 5.让思考4与思考2结合，之前放入的半条蚯蚓本来就比后面的长，还比后面的多长长几次，于是更不会影响有序性。 这样想通之后可以发现，如果用3个队列分别存"初始的蚯蚓，较长的半条蚯蚓，较短的半条蚯蚓"，在初始的蚯蚓sort完一遍后，3个队列从头到尾都会一直是有序的，不需要sort多次。

从"蚯蚓"遍grow()到简单运算

暴力的grow()就是让每一次的当前的蚯蚓的长度(不包括刚砍半的两个半条)都+q来维护长度。 转念一想，按照优化sort的思考2，既然每次生长都不会影响排序，那我这么勤奋的扫这么多遍维护为了什么呢！ 但是又发现，当我在输出蚯蚓长度的时候，一定是要长长之后的长度。 而且在用队列2,3之后，每一次放入的半条蚯蚓，它的长长情况都是不同的，先放入的半条蚯蚓总是比之后放入的蚯蚓多长几倍的q。那更不能完全不管长长了。 怎么办呢…

数组模拟队列,还能解决长长问题！

数组模拟队列的模板(模板代码写的不是很科学233)

//建立 int squeue[MAXN] //用来模拟队列的数组 int squeue_front=0; //队列的队首 int squeue_back=0; //队列的队尾(指向一个空项) //入队 squeue[squeue_back++]=x; //入队的数是x,在队尾放入x，随后队尾++ //得队首 int top=squeue[squeue_front]; //出队 squeue_front++; //队首后移一位,queue::pop()

如果我们用rnd这个整数代表doworm()的循环次数,那么…(用鼠标移到被下划线标记的运算有惊喜！) 对于worm[]，里面的第i条蚯蚓的长度就应该是 worm[i]+(rnd-1)*q 对于另外那两个数组cut1[],cut2[]，从下标0开始存半条蚯蚓，那么第i条的蚯蚓长度就应该是 cut1[i]+(rnd-2-i)*q 数组模拟队列真好用！

代码部分

全局变量们

int worm[100002]; //数组模拟队列,利用下标 int cut1[7000002]; int cut2[7000002]; //两个存切片的数组,cut1存更大的那个 int n,m,q,u,v,t; double p; int now_worm_cnt; //当前蚯蚓计数 int rnd; //doworm次数,以"rnd%t==0"来取代spc读秒的作用->空间优化? int worm_front,cut1_front,cut2_front; //worm,cut1,cut2的队首 int worm_back,cut1_back,cut2_back; //队尾

main()

scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t); now_worm_cnt=n; //现在有n条蚯蚓(废话) int ai; for(int i=1;i<=n;i++) { scanf("%d",&ai); worm[worm_back++]=ai; } sort(worm,worm+n,cmp); //排序一次即可 for(rnd=1;rnd<=m;rnd++) doworm(); doline2();

原来的print_answer()函数被我改成了doline2()，感觉更符合作用233

doworm()

int topworm=get_worm(); //找到出头虫 if(rnd%t==0) printf("%d ",topworm); //出头虫中周期成功上榜 cut(topworm);

这里将原来的spc记步器改成了rnd%t==0，概念都是每t步输出当前最长蚯蚓。

get_worm()

int tmp=-1; if(worm_front<n&&worm[worm_front]+(rnd-1)*q>=cut1[cut1_front]+(rnd-2-cut1_front)*q&&worm[worm_front]+(rnd-1)*q>=cut2[cut2_front]+(rnd-2-cut2_front)*q) { tmp=worm[worm_front++]+(rnd-1)*q; } else { if(cut1[cut1_front]+(rnd-2-cut1_front)*q>cut2[cut2_front]+(rnd-2-cut2_front)*q) { tmp=cut1[cut1_front]+(rnd-2-cut1_front)*q; cut1_front++; } else { tmp=cut2[cut2_front]+(rnd-2-cut2_front)*q; cut2_front++; } } return tmp;

get_worm()函数包含了取三个队列的最长队首与出队两个操作，除了那个突破天际的if条件有点吓人但是要这么写 其它的可以参照我的优化思想看懂！ tmp即表示当前最长的蚯蚓的长度

cut()

int len1 = floor(u*1.0/v*topworm); //floor(p*x) int len2 = topworm-len1; //x-floor(p*x) if(u*1.0/v>0.5) { cut1[cut1_back++]=len1; cut2[cut2_back++]=len2; } else { cut1[cut1_back++]=len2; cut2[cut2_back++]=len1; }

注释里表示运算的意义 这里是用if让cut1数组里永远存较长的半条，cut2数组永远存较短的半条

doline2()

printf("\n"); for(int i=1;i<=n+m;i++) { int topworm=get_worm(); if(i%t==0) printf("%d ",topworm); }

在m秒的处理后，蚯蚓总量会达到n+m条(每次砍半多一条) 此处再次调用get_worm()函数，继承了三个队列的当前队首值，rnd全局变量此时停留在m+1，发现意义刚好是"做了m遍砍半操作后(的查询)"，利用get_worm()可以完美读出m遍操作后三个队列里的蚯蚓当前长度。 i%t==0替换掉了原来的edT，原因是此时我们无法得到完整的每一条蚯蚓的正确长度与排序，需要一步一步搜索来得到topworm的值。

快乐AC

优化过后的时间复杂度大概是O(n)，已经可以完美解决题目数据了！ loj上速度暂时排名14，还没写读入和输出优化！ 如果对解法有什么问题，或者是蒟蒻我写题解的过程中出了写问题，或者是表扬我 ，别忘记在下方评论(｀・ω・´)！

---

STL的sort利用的应该是快排，时间复杂度为O(n)=nlog₂n，在还有一层for在外层的时候就已经是O(n²)了；更别说q有效的时候…无论如何，面对n+m<=7100000的数据显然是无法接受的… ↩︎