M_sea

洛谷2827 蚯蚓
Luogu分析堆很自然的想到维护一个堆,每次取出最大元素,然后切割后再插入回去。时间复杂度为$O((n+m)\lo...
扫描右侧二维码阅读全文
09
2017/09

洛谷2827 蚯蚓

Luogu

分析

很自然的想到维护一个堆,每次取出最大元素,然后切割后再插入回去。时间复杂度为$O((n+m)\log(n+m))$,能过大部分数据点。

正解

不难发现切割后的蚯蚓长度一定比原蚯蚓长度长,后切割的蚯蚓长度一定比先切割的蚯蚓长度短。

所以维护三个队列,分别保存未切割的蚯蚓和两段切割过的蚯蚓。
第一个队列只取,其它的又取又放。

每次在三个队列的队首取出一个最大的,切割后放入后两个队列中。

时间复杂度为$O(n+m)$。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long LL;
const int INF=2147483647;
int n,m,q,u,v,t,Add;
int que[3][8001000],head[3],tail[3]; //队列部分
inline int read() //读入优化
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
inline void write(int x) //输出优化
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}
inline bool cmp(const int x,const int y) { return x > y; }
inline int MaxValue() //取队首最大值
{
    int res=-INF,k;
    for (re int i=0;i<=2;++i)
         if (head[i]<tail[i]&&res<que[i][head[i]+1])
              res=que[i][head[i]+1],k=i;
    head[k]++; return res; //顺便队首++
}
int main()
{
    n=read(); m=read(); q=read(); u=read(); v=read(); t=read(); 
    for (re int i=1;i<=n;i++) que[0][++tail[0]]=read(); //输入
    sort(que[0]+1,que[0]+tail[0]+1,cmp); //排序,保证初始单调性
    for (re int i=1;i<=m;i++)
    {
        int x=MaxValue()+Add; //注意要加上增加长度
        if (i%t==0)
        {
            write(x);
            putchar((i+t>m)?'\n':' '); 
        }
        int l=(LL)x*u/v,r=x-l;  //注意l直接*u/v会爆int
        que[1][++tail[1]]=l-Add-q; //入队1
        que[2][++tail[2]]=r-Add-q; //同上
        Add+=q; //增加值更新
    }
    if (t>m) putchar('\n'); //特判换行
    for (re int i=1;i<=n+m;i++)
    {
        int x=MaxValue()+Add; //取最大值
        if (i%t==0) 
        {
            write(x); //输出
            putchar((i+t>n+m)?'\n':' '); //换行
        }
    }
    return 0;
}
最后修改:2018 年 11 月 30 日 08 : 59 PM

2 条评论

  1. wsm000

    链接该换了|´・ω・)ノ

    1. M_sea
      @wsm000

      以前的链接,懒得换了

发表评论