“卡常技术哪家强，中国OJ找洛谷”
去掉两个语句之后。。。95-->100
题目大意就不说了QWQ
首先65分裸优先队列，线段树，堆都可以。。。
100分：开三个队列，第一个存没被砍过的蚯蚓(要先sort)，第二个存被砍了长度*p的蚯蚓，第三个存被砍了长度*(1-p)的蚯蚓。每次都从三个队列的队头找一个最大的砍掉，然后分到第二个和第三个队列中。
怎么证明这样可以呢？其他博客有了详细的数学证明，但是我的思路很简单哇。。。假如某只蚯蚓x先被砍了，分成了两段，两段每秒都+q，等同于这只蚯蚓x每秒+2q，但是还没被砍的蚯蚓y每秒只+q，而x会比y先被砍肯定是原长度大于y，所以y砍掉之后的两条蚯蚓一定比所对应的x砍掉的两条蚯蚓要短，于是我们就能证明出三个队列都是单调的了。
然后就是坑爹的洛谷优化环节。。。可能是我比较蠢，处理+q这个操作我开了个数组表示某条蚯蚓被砍了几次，结果这样被洛谷卡成了95QAQ。。。可能很多大爷第一眼解法都是优化后的吧，我好菜啊。。。
优化：定义一个变量l，每次找出最长的蚯蚓长度ans+=l，砍完蚯蚓l+=q，然后砍成两段时两只蚯蚓入队要-=l，最后输出的时候所有蚯蚓长度要+=l。
于是优化掉了我的两个入队语句就过了。。。顺便一提队列用STL只有65分QAQ
代码如下：
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int inf=1<<31-1; int n,m,q,u,v,t,l,tot,num,maxj,a[4][15000010],now[4],nowr[4],b[15000010]; double p; bool cmp(int a,int b){return a>b;} int main() { scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);p=(double)u/v; for(int i=1;i<=n;i++)scanf("%d",&a[1][i]); sort(a[1]+1,a[1]+1+n,cmp); now[1]=now[2]=now[3]=1;nowr[1]=n; for(int i=1,ans=-inf;i<=m;i++,ans=-inf) { ++num; for(int j=1;j<=3;j++) if(now[j]<=nowr[j]) if(ans<a[j][now[j]])ans=a[j][now[j]],maxj=j; ans+=l;l+=q;now[maxj]++;a[2][++nowr[2]]=(int)floor(ans*p)-l;a[3][++nowr[3]]=(ans-(int)floor(ans*p))-l; if(num==t)printf("%d ",ans),num=0; } printf("\n"); num=0; for(int i=1,ans=-inf;i<=n+m;i++,ans=-inf) { ++num; for(int j=1;j<=3;j++) if(now[j]<=nowr[j]) if(ans<a[j][now[j]])ans=a[j][now[j]],maxj=j; now[maxj]++; if(num==t)printf("%d ",ans+l),num=0; } }
原文：http://www.cnblogs.com/Sakits/p/6498747.html
