NOIP2016Day2第2题 蚯蚓

Problem

Description Input Output Sample Input Sample Input1： 3 7 1 1 3 1 3 3 2 Sample Input2： 3 7 1 1 3 2 3 3 2 Sample Input3： 3 7 1 1 3 9 3 3 2 Sample Output Sample Output1： 3 4 4 4 5 5 6 6 6 6 5 5 4 4 3 2 2 Sample Output2： 4 4 5 6 5 4 3 2 Sample Output3 2 Data Constraint

Solution

我们建立三个队列，第一个队列是存原来的蚯蚓。 第二个队列我们存被切掉蚯蚓的第一部分， 第三个队列我们存被切掉蚯蚓的第二部分。 依次找出三个队列中最大的那个，将它切了。 对于q我们怎么处理呢？ 我们再开一维来维护被蚯蚓刚刚被切断时的时刻，然后真实长度自己算一下就行了。

Code

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define N 7100010 #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; int i,j,k,tot,l,n,m,q,t,u,v,z,xb,A; int a[N],h[N*2],ans1[N],ans2[N],st[3],en[3]; struct note { int val,start; }; note d1[N],d2[N],d[N]; bool cmp(note x,note y){return x.val>y.val;} int gv(int pos,int now) { if (pos==0) return d[st[pos]].val+(now-1-d[st[pos]].start)*q; if (pos==1) return d1[st[pos]].val+(now-1-d1[st[pos]].start)*q; if (pos==2) return d2[st[pos]].val+(now-1-d2[st[pos]].start)*q; } int gv1(int pos) { if (pos==0) return d[st[pos]].val+(m-d[st[pos]].start)*q; if (pos==1) return d1[st[pos]].val+(m-d1[st[pos]].start)*q; if (pos==2) return d2[st[pos]].val+(m-d2[st[pos]].start)*q; } int main() { freopen("earthworm.in","r",stdin); freopen("earthworm.out","w",stdout); scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t); fo(i,1,n) scanf("%d",&d[i].val); sort(d+1,d+n+1,cmp); st[0]=st[1]=st[2]=1;en[0]=n; fo(i,1,m) { xb=0;A=-2147483647; fo(j,0,2) if (gv(j,i)>A && st[j]<=en[j]) { xb=j; A=gv(xb,i); } st[xb]++; d1[++en[1]].val=(int)u*1.0/v*A; d2[++en[2]].val=A-d1[en[1]].val; d1[en[1]].start=d2[en[2]].start=i; if (i%t==0) printf("%d ",A); } printf("\n"); fo(i,1,n+m) { xb=0;A=-2147483647; fo(j,0,2) if (gv1(j)>A && st[j]<=en[j]) { xb=j; A=gv1(xb); } if (i%t==0) printf("%d ",A); st[xb]++; } }