M_sea

洛谷2827 蚯蚓
前言论改题改了一晚上发现没写等号然后重构代码再然后数组开小导致各种WA RE TLE的悲哀。。。题目描述本题中,我...
扫描右侧二维码阅读全文
09
2017/09

洛谷2827 蚯蚓

前言

论改题改了一晚上发现没写等号然后重构代码再然后数组开小导致各种WA RE TLE的悲哀。。。

题目描述

本题中,我们将用符号⌊c⌋表示对c向下取整。

蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为Ai(i=1,2,...,n),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。

每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为⌊px⌋和x−⌊px⌋的蚯蚓。特殊地,如果这两个数的其中一个等于0,则这个长度为0的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(是一个非负整常数)。

蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要m秒才能到来......(m为非负整数)

蛐蛐国王希望知道这m秒内的战况。具体来说,他希望知道:

•m秒内,每一秒被切断的蚯蚓被切断前的长度(有m个数)

•m秒后,所有蚯蚓的长度(有n+m个数)。

蛐蛐国王当然知道怎么做啦!但是他想考考你......

传送门

算法

暴力算法
用for解决所有问题,不再详述。


很自然的想到维护一个堆,每次取出最大元素,然后切割后再插入回去。时间复杂度为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 月 09 日 04 : 07 PM

发表评论