洛谷 P2827 蚯蚓题解

每日一题 day32 打卡

Analysis

我们可以想一下，对于每一秒除了被切的哪一个所有的蚯蚓都增长Q米，我们来维护3个队列，队列1表示最开始的蚯蚓，队列2表示每一次被切的蚯蚓被分开的较长的那一部分，队列3表示每一次被切的蚯蚓被分开的较短的那一部分。

我们先把原序列排序，因为不管怎么切，先被切的蚯蚓分成的两部分一定比后切的蚯蚓分成的两部分大(较大的部分和较大的部分比较，较小的部分和较小的部分比较)，所以我们可以省去每一秒增加每只蚯蚓的长度这个操作，转换成在查询砍那只蚯蚓时，把增加的长度算到蚯蚓的总长度上。

寻找每次砍哪一只蚯蚓就是在队列1、队列2、队列3的队头找一个算上增加的长度最大的蚯蚓，之后把他出队，切开的两部分分别进入队2、队3。

对于增量的计算我们可以按照蚯蚓在队列中的标号，因为队列1中的蚯蚓直到被切是一直处于一种增长状态，所以直接加上(当前时间-1) \* Q就可以了，而对于队列2和队列3的蚯蚓，他的增长是从被切掉那一刻的下一秒开始的，所以他的增长量则是(当前时间-1-被切割的时间)\*Q。

统计答案的时候把三个队列合并，排序输出就可以了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define maxm 7000000+10

 #define R register

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,m,q,u,v,t,sum;

 double p;

 int fir[maxm],sec[maxm],thi[maxm];

 int head1,head2,head3,tail1,tail2,tail3;

 priority_queue<int> que;

 inline bool cmp(int x,int y){return x>y;}

 inline int min_three(int x,int y,int z){return min(x,min(y,z));}

 inline int max_three(int x,int y,int z){return max(x,max(y,z));}

 int main()

 {

     n=read();m=read();q=read();u=read();v=read();t=read();

     for(R int i=;i<=n;i++) fir[i]=read();

     p=(double)u/v;

     sort(fir+,fir+n+,cmp);

     tail1=n;

     head1=head2=head3=;

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

     {

         int top=;

         if(head1>tail1)

         {

             if(sec[head2]>=thi[head3]) top=sec[head2],head2++;

             else if(sec[head2]<thi[head3]) top=thi[head3],head3++;

         }

         else if(fir[head1]>=sec[head2]&&fir[head1]>=thi[head3]) top=fir[head1],head1++;

         else if(sec[head2]>=fir[head1]&&sec[head2]>=thi[head3]) top=sec[head2],head2++;

         else if(thi[head3]>=fir[head1]&&thi[head3]>=sec[head2]) top=thi[head3],head3++;

         top+=sum;

         int a=floor(p*(double)top);

         int b=top-a;

         a-=q;b-=q;

         a-=sum;b-=sum;

         sec[++tail2]=a;

         thi[++tail3]=b;

         if(i%t==)

         {

             write(top);

             putchar(' ');

         }

         sum+=q;

     }

     putchar('\n');

     for(R int i=min_three(head1,head2,head3);i<=max_three(tail1,tail2,tail3);i++)

     {

         if(i>=head1&&i<=tail1) que.push(fir[i]);

         if(i>=head2&&i<=tail2) que.push(sec[i]);

         if(i>=head3&&i<=tail3) que.push(thi[i]);

     }

     int vol=que.size();

     for(R int i=;i<=vol;i++)

     {

         if(i%t==)

         {

             write(que.top()+sum);

             putchar(' ');

         }

         que.pop();

     }

     return ;

 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

巴特西

洛谷 P2827 蚯蚓题解

Analysis

最新文章

热门文章

巴特西

洛谷 P2827 蚯蚓 题解

Analysis

最新文章

热门文章

洛谷 P2827 蚯蚓题解