洛谷P2827 NOIp2016提高组 蚯蚓 题解【队列】【贪心】

作者: wjyyy 分类: 解题报告,贪心,队列 发布时间: 2018-07-09 15:16

点击量:23

 

   良心二叉堆有75分。。。

 

题目描述

本题中,我们将用符号

\(\lfloor c \rfloor \)表示对\(c\)向下取整,例如:\(\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3\)。

 

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

 

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

 

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

 

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

 

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

  • \(m\)秒内,每一秒被切断的蚯蚓被切断前的长度(有\(m\)个数);
  • \(m\)秒后,所有蚯蚓的长度(有\(n+m\)个数)。

 

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

输入输出格式

输入格式:

第一行包含六个整数 \(n,m,q,u,v,t\),其中:\(n,m,q\)的意义见【问题描述】;\(u,v,t\)均为正整数;你需要自己计算 \(p=u/v \)(保证 \(0<u<v\));\(t\)是输出参数,其含义将会在【输出格式】中解释。

 

第二行包含\(n\)个非负整数,为\(a_1, a_2, \dots, a_n\),即初始时\(n\)只蚯蚓的长度。

 

同一行中相邻的两个数之间,恰好用一个空格隔开。

 

保证\(1 \leq n \leq 10^5,0 \leq m \leq 7 \times 10^6,0<u<v \leq 10^9, 0 \leq q \leq 200, 1 \leq t \leq 71, 0 \leq a_i \leq 10^8\)。

 

输出格式:

第一行输出\(\left \lfloor \frac{m}{t} \right \rfloor\)个整数,按时间顺序,依次输出第\(t\)秒,第\(2t\)秒,第\(3t\)秒,……被切断蚯蚓(在被切断前)的长度。

 

第二行输出\(\left \lfloor \frac{n+m}{t} \right \rfloor\)个整数,输出\(m\)秒后蚯蚓的长度;需要按从大到小的顺序,依次输出排名第\(t\),第\(2t\),第\(3t\),……的长度。

 

同一行中相邻的两个数之间,恰好用一个空格隔开。即使某一行没有任何数需要输出,你也应输出一个空行。

 

请阅读样例来更好地理解这个格式。

输入输出样例

输入样例#1:
3 7 1 1 3 1
3 3 2
输出样例#1:
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
输入样例#2:
3 7 1 1 3 2
3 3 2
输出样例#2:
4 4 5
6 5 4 3 2
输入样例#3:
3 7 1 1 3 9
3 3 2
输出样例#3:
//空行
2

说明

【样例解释1】

在神刀手到来前:3只蚯蚓的长度为3,3,2。

 

1秒后:一只长度为3的蚯蚓被切成了两只长度分别为1和2的蚯蚓,其余蚯蚓的长度增加了1。最终4只蚯蚓的长度分别为(1,2),4,3 。括号表示这个位置刚刚有一只蚯蚓被切断。

 

2秒后:一只长度为4的蚯蚓被切成了1和3。5只蚯蚓的长度分别为:2,3,(1,3),4。

 

3秒后:一只长度为4的蚯蚓被切断。6只蚯蚓的长度分别为:3,4,2,4,(1,3)。

 

4秒后:一只长度为4的蚯蚓被切断。7只蚯蚓的长度分别为:4,(1,3),3,5,2,4。

 

5秒后:一只长度为5的蚯蚓被切断。8只蚯蚓的长度分别为:5,2,4,4,(1,4),3,5。

 

6秒后:一只长度为5的蚯蚓被切断。9只蚯蚓的长度分别为:(1,4),3,5,5,2,5,4,6。

 

7秒后:一只长度为6的蚯蚓被切断。10只蚯蚓的长度分别为:2,5,4,6,6,3,6,5,(2,4)。所以,7秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,6。7秒后,所有蚯蚓长度从大到小排序为6,6,6,5,5,4,4,3,2,2

 

【样例解释2】

这个数据中只有t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。

 

虽然第一行最后有一个6没有被输出,但是第二行仍然要重新从第二个数再开始输出。

 

【样例解释3】

这个数据中只有t=9与上个数据不同。

 

注意第一行没有数要输出,但也要输出一个空行。

 

【数据范围】

 

题解:

   首先看到每次切最长的蚯蚓,第一个想到的一定是二叉堆,仔细读题发现和m有关系,于是7e6的范围关上了二叉堆的大门。如果考场上想不到正解打了手写堆,是有可观的65分的。

 

   类似合并果子,合并果子是每次把最小的两个数合并,而这个题是把最大的一个数拆开(并且其他数还在增长)。既然合并果子可以用双队列来做到严格\(O(N\log N)\),那我们想办法把这个题做成差不多\(O(m\log m)\)的。

 

   联想合并果子的队列做法,首先把原来的序列排序在第一个序列中,然后从两个队列的队首四个元素中取最小的两个,放在第二个序列末尾。可以保证两个序列都是单调的,因为第一个序列是单调的,第二个序列一开始也是单调的。尽管是从两个序列中取最小的两个元素出来,但也至少不小于之前取出来的元素(序列本身就是单调的)。

 

   对于这个题来说,合并果子的逆操作一定不止两个队列,后入队的一定更长,来保证队列的单调性。因此我们分为3个队列,第一个队列按降序排列原来的蚯蚓,第二个队列放置比例为\(\lfloor px\rfloor \)的,第三个队列放比例为\(x-\lfloor px\rfloor\)的。尽管如此,如何证明先被分开的比后被分开所得到的更长呢?我们先理性地思考一下:蚯蚓在被分开后,它的总增长速度是\(2q/s\),而原增长速度为\(q/s\),同时先被分开的在被分开时就比后处理的要长一些,根据不等式的同向可加性,可以认为它是对的。

 

   再用数学证明一下,如果两条同样长的蚯蚓都满足这个条件,那么先被分开的蚯蚓更长时一定都满足这个条件。设蚯蚓长度为\(x;p,q\)同题意,现在队列1(按上一段的编号)中有两只长度为\(x\)的蚯蚓,第一秒过后,队列1中的蚯蚓只剩一只,长度为\(x+q\),队列2,队列3中的蚯蚓长度分别为\(\lfloor px\rfloor ,x-\lfloor px\rfloor\),第二秒开始时,此时队列1中的蚯蚓一定最长,剩下两个队列的蚯蚓都不超过\(x\)。第二秒过后,队列1没有蚯蚓,队列2中是\(\lfloor px\rfloor +q,\lfloor p(x+q)\rfloor\),队列3中是\(x-\lfloor px\rfloor +q,x+q-\lfloor p(x+q)\rfloor \)。因为\(p\le 1\),所以前面的蚯蚓总不比后面的短。

 

   因此,我们每次取三个队列里长度最大的,分开后再放到2,3中去。

 

   时间复杂度为\(O(n\log n+m)\)。代码里有一点可以优化,大Q数组是不需要的,队列q的下标就可以当作时间轴,每秒都有蚯蚓入队2,3。

 

Code:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define eps 1e-8
long long q[4][8200000],l[4],r[4];//队列
int Q[4][8200000];//进队时间(非必需)
bool cmp(long long x,long long y)
{
    return x>y;
}
int main()
{
    int n,m,u,v,T;
    long long qa;
    scanf("%d%d%lld%d%d%d",&n,&m,&qa,&u,&v,&T);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&q[1][i]);
        Q[1][i]=1;
    }
    std::sort(q[1]+1,q[1]+1+n,cmp);
    r[1]=n;
    double p=(u+0.0)/(v+0.0);
    long long b[4],part,k;
    for(int i=1;i<=m;i++)
    {
        b[1]=q[1][l[1]+1]+(i-Q[1][l[1]+1])*qa;//此时1队列队首元素大小
        b[2]=q[2][l[2]+1]+(i-Q[2][l[2]+1])*qa;//2
        b[3]=q[3][l[3]+1]+(i-Q[3][l[3]+1])*qa;//3
        if(l[1]!=r[1]&&b[1]>=b[2]&&b[1]>=b[3])//特判1
            k=1;
        else if((l[1]==r[1]||b[2]>=b[1])&&b[2]>=b[3])
            k=2;
        else
            k=3;
        long long t=q[k][++l[k]];
        t+=(i-Q[k][l[k]])*qa;
        if(i%T==0)
            printf("%lld ",t);

        part=t*p+eps;//有时加eps会错不知道什么情况
        q[2][++r[2]]=part;
        Q[2][r[2]]=i+1;
        q[3][++r[3]]=t-part;
        Q[3][r[3]]=i+1;
    }
    printf("\n");
    int cnt=0;
    while(l[1]!=r[1]||l[2]!=r[2]||l[3]!=r[3])
    {
        cnt++;
        b[1]=q[1][l[1]+1]+(m+1-Q[1][l[1]+1])*qa;
        b[2]=q[2][l[2]+1]+(m+1-Q[2][l[2]+1])*qa;
        b[3]=q[3][l[3]+1]+(m+1-Q[3][l[3]+1])*qa;
        if(l[1]!=r[1]&&(l[2]==r[2]||b[1]>=b[2])&&(l[3]==r[3]||b[1]>=b[3]))//细节比较多,防止越界
            k=1;
        else if(l[2]!=r[2]&&(l[1]==r[1]||b[2]>=b[1])&&(l[3]==r[3]||b[2]>=b[3]))
            k=2;
        else
            k=3;
        if(cnt%T==0)
            printf("%lld ",b[k]);
        l[k]++;
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */