题解 P2827 【蚯蚓】

算法具体不再过多赘述，可以证明每一种的蚯蚓长度都是单调的，开三个队列存一下，每次取出三个队头取最大。 其实这题用STL的queue是能A的。。。 注意一些地方的特判，不要RE。 ```cpp #include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<bitset> using namespace std; typedef long long ll; int a[100010],n,m,q,u,v,t; queue<int> qu,qu1,qu2; int nlen=0; inline int front(queue<int> &q) { if(q.empty()) return -0x3f3f3f3f; else return q.front()+nlen; } inline int get() { int mx=max(front(qu),max(front(qu1),front(qu2)));////notice特判，不要RE if(mx==front(qu)) qu.pop(); else if(mx==front(qu1)) qu1.pop(); else if(mx==front(qu2)) qu2.pop(); return mx; } inline bool cmp(int a,int b) { return a>b; } int main() { 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+1+n,cmp); for(int i=1;i<=n;i++) qu.push(a[i]); for(int i=1;i<=m;i++) { int tt=get(); int len1=(ll)tt*u/v; int len2=tt-len1; qu1.push(len1-nlen-q); //notice qu2.push(len2-nlen-q); //notice if(i%t==0) printf("%d ",tt); nlen+=q; } printf("\n"); for(int i=1;i<=n+m;i++) { int tt=get(); if(i%t==0) printf("%d ",tt); } printf("\n"); } ```