蚯蚓
蚯蚓
https://ac.nowcoder.com/acm/problem/16430
题意：
有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;
}
查看6道真题和解析
