[noip2016]蚯蚓<单调队列+模拟>

题目链接：https://vijos.org/p/2007

题目链接：https://www.luogu.org/problem/show?pid=2827#sub

说实话当两个网站给出AC后，我很感动。。。。这题啊，思路容易想到，就是小细节太烦了。。。。。

【思路】

这道题要开三个队列，而且需要证明到一个点才能够做。。

就是先切的蚯蚓的部分，比后切的蚯蚓的对应部分长。。。有可能你会想蚯蚓不是随时在长吗，当然这不影响。。我们来简单证明一下

------------------------------------------------证明部分-------------------------------------------------------

首先第一存初始的蚯蚓，x1>x2，先切x1,切完是x1*p（A部分）和x1-x1*p（B部分）,另外一个变长成为x2+q;

第二个时间点切原来x2这条，切完是(x2+q)*p（A部分）和x2+q-(x2+q)*p（B部分），第一条蚯蚓切后长成x1*p+q和x1-x1*p+q

然后来对应比较我们以A部分为例子 x1*p+q : (x2+q)*p=x2*p+q*p

由题意可以知道p的范围是0<p<1，所以x1*p>x2*p,q>q*p进一步得出所以 x1*p+q> (x2+q)*p，同理，切出来的另一半也是这样的。。

-----------------------------------------------------------------------------------------------------------------

所以我们只要不断的将新切出来的蚯蚓按A部分和B部分分别压入两个队列，那这两个队列都是单调队列

每次选择要切的蚯蚓只需要取这三个队列队首的最大值

第二个要考虑的问题就是蚯蚓长大的问题，为了更好的处理这个细节，我们对每一个蚯蚓对还原成最初状态，即在变长后切割完就减去当前的时间*q。。

减去以后，三个队列里的蚯蚓都是没有成长的状态，有可能有负数但是不影响。。。

【细节问题】

1.首先是数组范围，队列我没试过，但是我数组开10^6是runtime error了。后来开成10^7才通过

2.接着是用来找最大值的ans，就是用来更新并求最大值的一个变量（详细见代码），这个东东的初值要是10^9以上的，虽然题目说蚯蚓长小于10^8,但是在m秒后长大了

m*q的长度，这加起来就接近10^8次方了，所以这也是一个细节

3.还有就是把蚯蚓减回初识形态时，不仅要减去之前时间大家长大的长度，还要额外减去一个，因为被砍的蚯蚓当前这一秒是不会生长，相对于所有就要少一个q，为了保证最后所有的蚯蚓+m*q就是正确值，就要对当前切开的蚯蚓额外减去q

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<queue>

 #define maxn 100005

 #define maxm 700005

 #define maxv 10000005

 #define inf 2000000005

 using namespace std;

 int h[],t[],a[maxm];//h->指针，队首......t->队的长度

 int b[][maxv],n,m,q,u,v,tt,del;

 int comp(const void*a,const void*b){

     return (*(int*)a)<(*(int*)b)?:-;

 }

 int main(){

     scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&tt);

     h[]=h[]=h[]=;

     for(int i=;i<=n;i++)scanf("%d",&a[i]);

     a[]=inf;

     qsort(a,n+,sizeof(int),comp);

     for(int i=;i<=n;i++)b[][i]=a[i];

     t[]=n;

     for(int i=;i<=m;i++){

         int ans=-inf,num=;//num表示当前选出队首最大的那个队列序号

         for(int j=;j<=;j++){

             if(h[j]<=t[j]){//指针不越界

                 if(b[j][h[j]]>ans){

                     ans=b[j][h[j]];num=j;//找三个队列的队首最大值

                 }

             }

         }

         if(i%tt==)printf("%d ",ans+del);

         h[num]++;//理解为删除操作

         b[][++t[]]=(long long)(ans+del)*u/v-del-q;//队尾压入一个切开的A值

         b[][++t[]]=ans+del-(long long)(ans+del)*u/v -del-q;//队尾压入一个切开的B值

         del+=q;

     }

     printf("\n");

     for(int i=;i<=n+m;i++){

         int ans=-inf,num=;

         for(int j=;j<=;j++){

             if(h[j]<=t[j]&&b[j][h[j]]>ans){

                 ans=b[j][h[j]];num=j;

             }

         }

         if(i%tt==){    printf("%d ",ans+del);}

         h[num]++;

     }

     return ;

 }

【总结】

1.对于一道题，要分析数据的变化，就像这题中蚯蚓的长度一样，不是始终小于题所给的10^8，所以要分析全局来赋值

2.数组的大小要严谨分析，在不会爆内存的情况下可以多开，虽然我刚刚开始开的是n+m大小，但是因为不会删去之前的蚯蚓，所以这个大小还不够，还是会越界

3.很多题是带有结论的，需要去证明，所以不要盲目去做一题，稍加分析，当然也可以先打暴力来辅助分析

巴特西

[noip2016]蚯蚓<单调队列+模拟>

最新文章

热门文章