题意:
有n条蚯蚓,在m秒内每一秒选择最长的一条蚯蚓分成二份,其余蚯蚓增长q长度,然后按要求输出。
思路:
用二个队列进行模拟,维护二个队列的单调性,一个队列加入长的,另一个队列加入短的,这样二个队列就是单调的,队列中保持0时刻的长度。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e12;
ll a[100005];
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
int n, m, q, u, v, t;
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
double p=u*1.0/v;
queue <ll>q1, q2;
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
sort(a,a+n,cmp);
int ji=0;
for(int i=1;i<=m;i++)
{
ll ma=-inf;
if(ji<n)
{
ma=max(a[ji],ma);
}
if(!q1.empty())
{
ma=max(q1.front(),ma);
}
if(!q2.empty())
{
ma=max(q2.front(),ma);
}
if(ji<n&&ma==a[ji])
{
ji++;
}
else if(!q1.empty()&&q1.front()==ma)
{
q1.pop();
}
else
{
q2.pop();
}
ma=ma+(i-1)*q;
if(i%t==0)
{
//printf("i=%lld t=%d\n",i,t);
printf("%lld%c",ma,m/t==i/t?'\n':' ');
}
ll l=floor(ma*p), r=ma-l;
q1.push(l-i*q);
q2.push(r-i*q);
}
if(m<t)
{
printf("\n");
}
for(int i=1;i<=m+n;i++)
{
ll ma=-inf;
if(ji<n)
{
ma=max(a[ji],ma);
}
if(!q1.empty())
{
ma=max(q1.front(),ma);
}
if(!q2.empty())
{
ma=max(q2.front(),ma);
}
if(ji<n&&ma==a[ji])
{
ji++;
}
else if(!q1.empty()&&q1.front()==ma)
{
q1.pop();
}
else
{
q2.pop();
}
ma=ma+m*q;
if(i%t==0)
{
printf("%lld%c",ma,(m+n)/t==i/t?'\n':' ');
}
}
if(m+n<t)
{
printf("\n");
}
return 0;
}

京公网安备 11010502036488号