NOIP2016Day2T2蚯蚓(队列+坑爹洛谷毁我青春)

　　“卡常技术哪家强，中国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=<<-;

int n,m,q,u,v,t,l,tot,num,maxj,a[][],now[],nowr[],b[];

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=;i<=n;i++)scanf("%d",&a[][i]);

    sort(a[]+,a[]++n,cmp);

    now[]=now[]=now[]=;nowr[]=n;

    for(int i=,ans=-inf;i<=m;i++,ans=-inf)

    {

        ++num;

        for(int j=;j<=;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[][++nowr[]]=(int)floor(ans*p)-l;a[][++nowr[]]=(ans-(int)floor(ans*p))-l;

           if(num==t)printf("%d ",ans),num=;

    }

    printf("\n");

    num=;

    for(int i=,ans=-inf;i<=n+m;i++,ans=-inf)

    {

        ++num;

        for(int j=;j<=;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=;

    }

}