我们可以想一下,对于每一秒除了被切的哪一个所有的蚯蚓都增长Q米,我们来维护3个队列,队列1表示最开始的蚯蚓,队列2表示每一次被切的蚯蚓被分开的较长的那一部分,队列3表示每一次被切的蚯蚓被分开的较短的那一部分。
我们先把原序列排序,因为不管怎么切,先被切的蚯蚓分成的两部分一定比后切的蚯蚓分成的两部分大(较大的部分和较大的部分比较,较小的部分和较小的部分比较),所以我们可以省去每一秒增加每只蚯蚓的长度这个操作,转换成在查询砍那只蚯蚓时,把增加的长度算到蚯蚓的总长度上。
寻找每次砍哪一只蚯蚓就是在队列1、队列2、队列3的队头找一个算上增加的长度最大的蚯蚓,之后把他出队,切开的两部分分别进入队2、队3。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
deque< int > v1;
deque< int > v2;
deque< int > v3;
ll n,m,q,u,vv,t;
double p;
bool lxl(int a,int b)
{
return a>b;
}
int kkk()
{
int ans=-999999999;
if(v1.size())
ans=max(ans,v1.front());
if(v2.size())
ans=max(ans,v2.front());
if(v3.size())
ans=max(ans,v3.front());
if(v1.size()&&ans==v1.front())
{
v1.pop_front();
return ans;
}
if(v2.size()&&ans==v2.front())
{
v2.pop_front();
return ans;
}
if(v3.size()&&ans==v3.front())
{
v3.pop_front();
return ans;
}
}
int a[1000005];
int main()
{
cin>>n>>m>>q>>u>>vv>>t;
p=1.0*u/vv;
for(ll i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,lxl);
for(ll i=1;i<=n;i++)
{
v1.push_back(a[i]);
}
for(ll i=1;i<=m;i++)
{
int lxl=kkk();
if(i%t==0)
printf("%d ",lxl+(i-1)*q);
int MIN=min(floor(p*(lxl+(i-1)*q)-i*q),lxl-floor(p*(lxl+(i-1)*q))-q);
int MAX=max(floor(p*(lxl+(i-1)*q)-i*q),lxl-floor(p*(lxl+(i-1)*q))-q);
v2.push_back(MAX);
v3.push_back(MIN);
}
cout<<"\n";
for(ll i=1;v1.size()||v2.size()||v3.size();i++)
{
int lxl=kkk();
if(i%t==0)
printf("%d ",lxl+m*q);
}
cout<<"\n";
return 0;
}