2016noip蚯蚓《单调队列》

题目

思路：三队列模拟；

d1存初始蚯蚓，d2存新生蚯蚓A，d3存新生蚯蚓B，d1队列只取不放；（这里可以证明d2，d3是单调的）

第一篇博客，写的很差。
。。。。。。。
思路就是：把前面的+q转变为新生的 -i*q.（这样大小关系是一样的）
最后输出的时候+上相应的Q就行了就行了

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<ctime>
using namespace std;
int my_comp(int a,int b)
{
if(a>b) return 1;
return 0;
}
int d1[9*1000000],d2[9*1000000],d3[9*1000000];
int main()
{
int n,m,q,u,v,t,i,j,t1,l1,l2,l3;

freopen("earthworm.in","r",stdin);
freopen("earthworm.ans","w",stdout);

memset(d1,128,sizeof(d1));
memset(d2,128,sizeof(d2));
memset(d3,128,sizeof(d3));

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

l1=l2=l3=1;

for(i=1;i<=n;i++)
 scanf("%d",&d1[i]);
 
t1=t; 

sort(d1+1,d1+n+1,my_comp);
 
for(i=1;i<=m;i++)
{
long long x1,x2,c,q1=d1[l1],q2=d2[l2],q3=d3[l3];
if(q1>=q2&&q1>=q3) {x1=d1[l1];l1++;} 
 else
  {
   if(q2>=q1&&q2>=q3) {x1=d2[l2];l2++;}
    else              {x1=d3[l3];l3++;} 
  }

   long long a=(x1+=(i-1)*q)*u/v;

d2[i]=a-i*q;
d3[i]=x1-a-i*q;

if(i%t==0) printf("%d ",x1);
} 

printf("\n");

for(i=1;i<=n+m;i++)
{
int x1,x2,c,q1=d1[l1],q2=d2[l2],q3=d3[l3];
if(q1>=q2&&q1>=q3) {x1=d1[l1];l1++;} 
 else
  {
   if(q2>=q1&&q2>=q3) {x1=d2[l2];l2++;}
    else              {x1=d3[l3];l3++;} 
  }

if(i%t==0) printf("%d ",x1+m*q);
}

fclose(stdin);
fclose(stdout);

return 0;
}

我被坑了好几次。QAQ

首先在x1*u/v时有可能爆int 类型。然后因为切开的蚯蚓都另外减去了增加值所以有可能是负值，当某一队蚯蚓取完时，0一定比负值大。于是指针就会卡到某个队列里啊。错是必然的。这个题让我惊醒了，真的，会打代码是一方面，重要的是分析啊，还有数据的范围和判断。希望以后不会犯这种错误了QAQ。