蚯蚓

代码链接

我们发现枚举每一次的操作几乎是必要的,因为没有什么规律

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e7;
bool com(int a,int b){
    return a>b;
}
int n,m,qq,u,v,now,tt;
int ans[maxn],h[4],t[4],q[4][maxn];
double p;
void run(int x)
{
    int sumn=0,num=0;//找当前最大 
    for(int i=1;i<=3;i++)
    {
        if( i==1&&q[i][h[i]]+x*qq>sumn && h[i]<t[i] )
            num=i,sumn=q[i][h[i]]+x*qq;
        else if( q[i][h[i]]+(x-h[i])*qq>sumn&& h[i]<t[i] )
            num=i,sumn=q[i][h[i]]+(x-h[i])*qq;
    }
    ans[x+1]=sumn,now=sumn,q[num][h[num]++];//找最大,h[num]++是排除元素 
}
signed main()
{
    cin >> n >> m >> qq >> u >> v >> tt;
    p=u*1.0/v;
    for(int i=1;i<=3;i++ )    h[i]=t[i]=1;
    for(int i=1;i<=n;i++)
        scanf("%lld",&q[1][i]);
    t[1]=n+1;
    sort(q[1]+1,q[1]+1+n,com);
    for(int i=1;i<=m;i++)
    {
        run(i-1);
        int one=(int)now*p,two=now-one;
        if( one<two )    swap(one,two);
        q[2][t[2]++]=one,q[3][t[3]++]=two;//加到队尾 
    }
    for(int i=tt;i<=m;i+=tt)
        printf("%lld ",ans[i] );
    cout << '\n';
    int top=0;
    for(int i=1;i<=3;i++)
    for(int j=h[i];j<t[i];j++ )
    {
        if( i==1&&h[i]<t[i] )    ans[++top]=q[i][j]+m*qq;
        else if( h[i]<t[i] )    ans[++top]=q[i][j]+(m-j)*qq;    
    }
    sort(ans+1,ans+1+top,com);
    for(int i=tt;i<=n+m;i+=tt )
        printf("%lld ",ans[i] );
}