【noip2016】蚯蚓（单调性+队列）

题目贼长

大意是你有n个线段，每一秒你要拿出来最长的一个线段切成两段长度为[pu](向下取整）和u-[pu]两段（其中u是线段长，p是一个大于0小于1的实数）没被切的线段长度加q（0<q<200）。问m秒后的n+m条线段的长度（1≤n≤100000,1<=m<=7000000)

题解

乍一看是堆，可是堆被卡了。

我们建三个队列分别装最初的线段，和被切出来的两种线段。可以发现任何时候，一个队列里的线段长度单调递减，最长的线段，就从这三个队列里取出第一个比较就行。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 long long n,m,q,u,v,t,z[N],qu1[N],qu2[N],qu3[N],h1,h2,h3,t1,t2,t3,cnt2[N],cnt3[N];

 bool cmp(long long x,long long y){

     return x>y;

 }

 int main(){

     scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);

     for(long long i=;i<=n;i++){

         scanf("%lld",&z[i]);

     }

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

     for(long long i=;i<=n;i++){

         qu1[++t1]=z[i];

     }

     h1=h2=h3=;

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

         long long a=qu1[h1]+(i-)*q;

         if(h1>t1)a=;

         long long b=qu2[h2]+(i-cnt2[h2]-)*q;

         if(h2>t2)b=;

         long long c=qu3[h3]+(i-cnt3[h3]-)*q;

         if(h3>t3)c=;

         long long d=max(a,max(b,c));

         if(d==a)h1++;

         else if(d==b)h2++;

         else h3++;

         long long e=(long long)d*u/v;

         long long f=d-e;

         qu2[++t2]=e;

         qu3[++t3]=f;

         cnt2[t2]=cnt3[t3]=i;

         if(i%t==)printf("%lld ",d);

     }

     printf("\n");

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

         long long a=qu1[h1]+m*q;

         if(h1>t1)a=;

         long long b=qu2[h2]+(m-cnt2[h2])*q;

         if(h2>t2)b=;

         long long c=qu3[h3]+(m-cnt3[h3])*q;

         if(h3>t3)c=;

         long long d=max(a,max(b,c));

         if(d==a)h1++;

         else if(d==b)h2++;

         else h3++;

         if(i%t==)printf("%lld ",d);

     }

     return ;

 }

巴特西

【noip2016】蚯蚓（单调性+队列）

题目贼长

大意是你有n个线段，每一秒你要拿出来最长的一个线段切成两段长度为[pu](向下取整）和u-[pu]两段（其中u是线段长，p是一个大于0小于1的实数）没被切的线段长度加q（0<q<200）。问m秒后的n+m条线段的长度（1≤n≤100000,1<=m<=7000000)

题解

乍一看是堆，可是堆被卡了。

我们建三个队列分别装最初的线段，和被切出来的两种线段。可以发现任何时候，一个队列里的线段长度单调递减，最长的线段，就从这三个队列里取出第一个比较就行。

最新文章

热门文章