洛谷 P2827 [NOIP2016]蚯蚓

二话不说直接开干

首先，这个数据范围不小，如果使用堆或优先队列对所有的蚯蚓进行暴力维护的话将会导致$O(m\log (n+m))$的复杂度——这个常不好卡。 所以我们想办法找到线性复杂度的做法。 观察每次剪断后的蚯蚓，假设$a,b$是相继两段要被剪断的蚯蚓 $a$被剪成$a_1=ap$与$a_2=a(1-p)$ $b$被剪成$b_1=(b+q)p$与$b_2=(b+q)(1-p)$ 假设$p>\frac{1}{2}$，观察$a_1,b_1$和$a_2,b_2$大小关系： 当$b_1,b_2$入队时，$a_1,a_2$已经长长了$q$ 故$a_1=ap+q,a_2=a(1-p)+q$ $b_1=bp+pq,b_2=b(1-p)+q-pq$ 对于$a_1,b_1$，显然$ap>bp,q>pq$，故$a_1>b_1$ 对于$a_2,b_2$，同时减去$q$后$a>b,-pq<0$，故$a_2>b_2$ 所以，其实所有剪短之后的蚯蚓都是按照长短顺序单调入队的！ 接下来的做法就不难了： 开三个队列$A,B,C$，分别为原蚯蚓、剪断后$ap$部分的蚯蚓和剪断后$a(1-p)$的蚯蚓 先给$A$排个序，然后每次从三个队列中挑一条最长的剪。 为了表现蚯蚓的生长，用一个变量$delta(\Delta )$记录自一开始以来生长的长度 假设有两条蚯蚓$x,y$，$x$在队列中，$y$是刚刚产生的，而且原始状态下$x=y$。 $x^{\prime }$为$x$在队列中储存的长度，其实际长度$x$为$x^{\prime }+\Delta$ 在这一秒内，$y$出生了，然而$x$已经生长，于是我们先让$\Delta$增加为${\Delta }_2$，再使得$y^{\prime }=y-{\Delta }_2$ 那么，现在再取出$x$的话，得到的结果将是$x^{\prime }+{\Delta }_2$，即$x+p$，而$y$取出时结果仍然是$y$ 生长就完成了

#include<cstdio> //#include<queue> #include<algorithm> #include<functional> using namespace std; int a[110000];long long delta; template<typename Tp> struct queue//超奥义玄学手打队列 { int head,tail; /*/For debugging Tp list[110]; queue():head(1),tail(0){} /*///For judging Tp *list; queue():head(1),tail(0),list(new Tp[11110000]){} //*/ int size(){return tail-head+1;} int front(){return list[head];} void pop(){++head;} void push(Tp x){list[++tail]=x;} }; queue<long long>qa,qb,qc; int getmax() { long long maxa=-1,maxb=-1,maxc=-1; if(qa.size())maxa=qa.front()+delta; if(qb.size())maxb=qb.front()+delta; if(qc.size())maxc=qc.front()+delta; if(maxa>=maxb&&maxa>=maxc) /* 这地方一开始打了大于号，于是挂了好久 如果打了大于号的话会优先用c……然后两个-1就给我炸了 */ { qa.pop(); return maxa; } if(maxb>=maxa&&maxb>=maxc)// { qb.pop(); return maxb; } qc.pop(); return maxc; } int main() { int n,m,q,u,v,t; scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t); for(int i=1;i<=n;i++) scanf("%d",a+i); sort(a+1,a+n+1,greater<int>()); for(int i=1;i<=n;i++) qa.push(a[i]); for(int i=1;i<=m;i++) { long long now=getmax(); if(i%t==0)printf("%lld ",now); long long nowb=now*u/v,nowc=now-nowb; if(nowb<nowc)swap(nowb,nowc); delta+=q; qb.push(nowb-delta); qc.push(nowc-delta); } putchar(10); for(int i=1;i<=n+m;i++) { long long now=getmax(); if(i%t==0) printf("%lld ",now); } putchar(10); return 0; }