题解 P2827 【蚯蚓】

aiyougege · 2018-05-01 11:06:33 · 题解

蚯蚓

80分

　　首先这道题可以用合并果子的思路做, 合并果子是找到两个最小的并合并, 而这道题是找到最大的拆分.实际上是差不多的.

　　如何处理每次的将每只蚯蚓加一定长度呢?或许可以转变思路, 每次只有两只蚯蚓没被加其他的全部被加了, 根据运动是相互的, 除了那被切成的两只蚯蚓其他的都往正方向移动了一些, 等价于那两只往负方向移动了一些. 所以可以记录累计加的长度, 有几只没被加的就减去就好了.

　　利用堆或者是优先队列, 保存每只蚯蚓, 然后每次切断就弹出堆顶元素(蚯蚓)拆成两只后放入堆.这样做的时间复杂度大概是O(m\log_2 n).根据一些小细节的处理当然有快有慢.我前前后后改了不少小细节大概是交了七次.这么做大概就是得到80-85分了.

100分

　　关键点: 发现此题中隐含的单调性.

　　发现先被切掉的蚯蚓分成的蚯蚓一定比后切掉的蚯蚓分成的蚯蚓大. 　　假设这两只蚯蚓分别为a,b,其中a>b.那么它被切成a_1,a_2.　t秒后, b被切成了b_1,b_2.此时a_1,a_2的长度为l_{a_1}+t=pl_{a}+t,l_{a_2}+t=(1-p)l_a+t.而b_1,b_2的长度却为p(l_b+t),(1-p)(1_b+t), 容易看出l_{a_1}>l_{b_1},l_{a_2}>l_{b_2}.也就是说根本不需要用一个堆来维护, 它本来就具有一定单调性.

　　那么就是说如果蚯蚓a_1,a_2,\cdots,满足a_1>a_2>\cdots,那么以此分成两只a_{11},a_{12},a_{21},a_{22},\cdots .那么a_{12}>a_{22}>\cdots,a_{11}>a_{21}>\cdots

　　那么就可以将这两堆依次存储, 加上还没被切过的蚯蚓.每次要切时在这三堆里面选择最大的, 切完再依次放回去. 　　所以这么做时间复杂度为O(m).再优化一下细节基本上就没问题了.

　　结论: 善于发现题目中隐含的单调性.

　　Tip:有些细节需要仔细考虑不然会很惨

Code

80分

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;

priority_queue<int>ans;//优先队列
int n,m,q,u,v,t;
int sigma;//累计加的
double p;
int tot;

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=(double)u/v;int tmp;
    for(int i=1;i<=n;++i){
        scanf("%d",&tmp);
        ans.push(tmp);
    }
    for(int i=1;i<=m;++i){
        int top=ans.top()+sigma;//被切的蚯蚓的长度
        ans.pop();
        int a1=floor(p*(double)top),a2=top-a1;//被切成的两只的长度
        a1-=sigma,a2-=sigma;
        a1-=q,a2-=q;//需要减去它们俩没加的
        ans.push(a1),ans.push(a2);//放回队列
        if(i%t==0)printf("%d ",top);//要求输出的第一行
        sigma+=q;//累加
    }
    putchar('\n');//换行
    for(int i=1;ans.size();++i){
        if(i%t==0)printf("%d ",ans.top()+sigma);//要求输出的第二行
        ans.pop();
    }
    return 0;
}

100分

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 7000005
using namespace std;

bool cmp(const int &a,const int &b){
    return a>b;
}

priority_queue<int>ans;
int cut1[N],now[N],cut2[N];
int n,m,q,u,v,t;
int sigma;
double p;
int h,h1,h2;
int t0,t1,t2;

int main(){
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    p=(double)u/v;int tmp;
    for(t0=1;t0<=n;++t0)
        scanf("%d",&now[t0]);
    --t0;t1=t2=0;h=h1=h2=1;
    sort(now+1,now+t0+1,cmp);//对所有蚯蚓从大到小排序
    int top;
    for(int i=1;i<=m;++i){
        if(h>t0){if(cut1[h1]>cut2[h2])top=cut1[h1++];else top=cut2[h2++];}
        else if(now[h]>=cut1[h1]&&now[h]>=cut2[h2])top=now[h],++h;
        else if(cut1[h1]>=cut2[h2]&&now[h]<=cut1[h1])top=cut1[h1],++h1;
        else top=cut2[h2],++h2;
        ;;;//上述四行都是为了找到应该被切的蚯蚓,写的麻烦细节很多
        top+=sigma;
        int a1=floor(p*(double)top),a2=top-a1;
        sigma+=q;
        a1-=sigma,a2-=sigma;
        cut1[++t1]=a1,cut2[++t2]=a2;
        if(i%t==0)printf("%d ",top);
    }
    putchar('\n');
    for(int i=h;i<=t0;++i)ans.push(now[i]);
    for(int i=h1;i<=t1;++i)ans.push(cut1[i]);
    for(int i=h2;i<=t2;++i)ans.push(cut2[i]);
    for(int i=1;ans.size();++i){
        if(i%t==0)printf("%d ",ans.top()+sigma);
        ans.pop();
    }
    return 0;
}