题解 P2827 【蚯蚓】

EarthGiao · 2019-08-07 21:16:14 · 题解

先分析一下题意：

这个题说的就是一开始给你很多条蚯蚓，然后给出你规定的次数，每一次都从蚯蚓里面拿出最长的来切成一条是原来q倍的，另一条是原来的（1 - q）倍，把切开的两条再放回去。规定次数完成之后，再将剩余的全部蚯蚓从大到小顺序输出，就是酱紫QWQ

可以看出，有一种很暴力很简单的方法，将每一条蚯蚓的长度都放入一个大根堆（优先队列）中，然后从1 - m次每一次都从堆顶（队首）取出最长的那条蚯蚓然后按照给出的u,v切开再放回大根堆（优先队列），这里的大根堆和优先队列都是可以直接排序的只需要将数放进去就好了，这样暴力m次。m次完成之后，从堆顶（队首）每一次输出堆顶（队首）的数，然后弹出知道堆空（队列空）结束了。

没有这么简单！！！！！！

在剪断一条蚯蚓的同时其他的蚯蚓还会长大！！！马上就会想到是区间修改， 因为出现了区间修改，不过这个区间是一定的，一定是除了最大的那个之外的， 所以可以只在最大的那一个上面最手脚，毕竟只有一个， 所以修改起来也是容易的很多， 可以每一次 不增加只记录增加次数最后用到的时候再加 那么那个不加的怎么办呢？ 可以减去需要加的数，这样就很巧妙了，可以和别的一样加上相同的数，同时还可以让排序是正确的 不然别的都没加那么就会影响排序

代码

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;
priority_queue<int>q;
int main()
{
    int n,m,qq,u,v,t;
//n:蚯蚓数 ; m : m秒内的状况 ; q ：其余蚯蚓增加的长度  
    int qwq; 
    scanf("%d%d%d%d%d%d",&n,&m,&qq,&u,&v,&t);
    double p;
    p = u * 1.0 / v;
    for(int i = 1;i <= n;++ i)
    {
        scanf("%d",&qwq);
        q.push(qwq);
    }
    int jss = 0;
    while(m --) 
    {
        int awa = q.top() + jss * qq;
        jss ++;
        if(jss % t == 0)
            printf("%d ",awa);
        q.pop();
        int X1 = awa * p;
        int aa = X1 - jss * qq;
        int bb = (awa - X1) - jss * qq;
        q.push(aa);q.push(bb);
    }
    printf("\n");
    int js = 0;
    while(!q.empty())
    {
        js ++;
        if(js % t == 0)
            printf("%d ",q.top() + jss * qq);
        q.pop();
    }
    printf("\n");
    return 0;
}

不过很好的是，只有85分，三个点都是1.2s，就超了一丢丢只需要优化一下下就好了。

但是可以怎么优化呢？

其实这里可以发现一种很显然的单调性，如果你将一开始的蚯蚓排好序 那么前一条蚯蚓切出来的两条蚯蚓一定各自 大于等于后面一条蚯蚓切出来的两条蚯蚓 毕竟前一条蚯蚓一定大于等于后面那一个，所以切出来的分半放在两个数组中和后面对应的切出来的两条也一定是大于等于的 所以可以设置三个单调队列（或者sort排序然后用数组储存） 每一次切得时候都从三个队列里面找最大的切就好了

AC代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
const int M1 = 1e5 + 5;
const int M2 = 8e6;
using namespace std;
int a[M1];
int b[M2];
int c[M2];
bool cmp(int x,int y)
{
    return x > y;
}
int main()
{ 
    int n,m,qq,u,v,t;
//n:蚯蚓数 ; m : m秒内的状况 ; q ：其余蚯蚓增加的长度  
    int qwq; 
    scanf("%d%d%d%d%d%d",&n,&m,&qq,&u,&v,&t);
    a[n + 1] = -0x7fffffff;
    double p;
    p = u * 1.0 / v;
    for(int i = 1;i <= n;++ i)
        scanf("%d",&a[i]);
    sort(a + 1,a + n + 1,cmp);
    int js = 0;
    int ja = 1;
    int jb = 1,tb = 0;
    int jc = 1,tc = 0;
    int Max;
    int zuobiao;
    while(m --)
    {
        if(a[ja] >= b[jb] && a[ja] >= c[jc])
        {
            Max = a[ja];
            ja ++;
        }
        else
        if(b[jb] >= a[ja] && b[jb] >= c[jc])
        {
            Max = b[jb];
            jb ++;
        }
        else
        if(c[jc] >= a[ja] && c[jc] >= b[jb])
        {
            Max = c[jc];
            jc ++;
        }
        int awa = Max + js * qq;
        js ++;
        if(js % t == 0)
            printf("%d ",awa);
        int X1 = awa * p;
        b[++ tb] = X1 - js * qq;
        c[++ tc] = (awa - X1) - js * qq;
    }
    printf("\n");
    int ans = 0;
    for(int i = ja;i <= n;++ i)a[i] += qq * js;
    for(int i = jb;i <= tb;++ i)b[i] += qq * js;
    for(int i = jc;i <= tc;++ i)c[i] += qq * js;
    b[tb + 1] = -0x7fffffff;
    c[tc + 1] = -0x7fffffff;
    while(ja <= n || jb <= tb || jc <= tc)
    {
        ans ++;
        if(a[ja] >= b[jb] && a[ja] >= c[jc] && ja <= n)
        {
            if(ans % t == 0)
                printf("%d ",a[ja]);
            ja ++;
        }
        else
        if(b[jb] >= a[ja] && b[jb] >= c[jc] && jb <= tb)
        {
            if(ans % t == 0)
                printf("%d ",b[jb]);
            jb ++;
        }
        else
        if(c[jc] >= a[ja] && c[jc] >= b[jb] && jc <= tc)
        {
            if(ans % t == 0)
                printf("%d ",c[jc]);
            jc ++;
        }
    }
    printf("\n");
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
const int M1 = 1e5 + 5;
const int M2 = 8e6;
using namespace std;
int a[M1];
int b[M2];
int c[M2];
bool cmp(int x,int y)
{
    return x > y;
}
int main()
{ 
    int n,m,qq,u,v,t;
//n:蚯蚓数 ; m : m秒内的状况 ; q ：其余蚯蚓增加的长度  
    int qwq; 
    scanf("%d%d%d%d%d%d",&n,&m,&qq,&u,&v,&t);
    a[n + 1] = -0x7fffffff;
    double p;
    p = u * 1.0 / v;
    for(int i = 1;i <= n;++ i)
        scanf("%d",&a[i]);
    sort(a + 1,a + n + 1,cmp);
    int js = 0;
    int ja = 1;
    int jb = 1,tb = 0;
    int jc = 1,tc = 0;
    int Max;
    int zuobiao;
    while(m --)
    {
        if(a[ja] >= b[jb] && a[ja] >= c[jc])
        {
            Max = a[ja];
            ja ++;
        }
        else
        if(b[jb] >= a[ja] && b[jb] >= c[jc])
        {
            Max = b[jb];
            jb ++;
        }
        else
        if(c[jc] >= a[ja] && c[jc] >= b[jb])
        {
            Max = c[jc];
            jc ++;
        }
        int awa = Max + js * qq;
        js ++;
        if(js % t == 0)
            printf("%d ",awa);
        int X1 = awa * p;
        b[++ tb] = X1 - js * qq;
        c[++ tc] = (awa - X1) - js * qq;
    }
    printf("\n");
    int ans = 0;
    for(int i = ja;i <= n;++ i)a[i] += qq * js;
    for(int i = jb;i <= tb;++ i)b[i] += qq * js;
    for(int i = jc;i <= tc;++ i)c[i] += qq * js;
    b[tb + 1] = -0x7fffffff;
    c[tc + 1] = -0x7fffffff;
    while(ja <= n || jb <= tb || jc <= tc)
    {
        ans ++;
        if(a[ja] >= b[jb] && a[ja] >= c[jc] && ja <= n)
        {
            if(ans % t == 0)
                printf("%d ",a[ja]);
            ja ++;
        }
        else
        if(b[jb] >= a[ja] && b[jb] >= c[jc] && jb <= tb)
        {
            if(ans % t == 0)
                printf("%d ",b[jb]);
            jb ++;
        }
        else
        if(c[jc] >= a[ja] && c[jc] >= b[jb] && jc <= tc)
        {
            if(ans % t == 0)
                printf("%d ",c[jc]);
            jc ++;
        }
    }
    printf("\n");
    return 0;
}