题解 P2827 【蚯蚓】

· · 题解

先来一个35分的纯暴力：

#define ll long long
#define p u*1.0/v
using namespace std;

ll n,m,q,u,v,t;
priority_queue<ll> Q;

int main(){
//  freopen("earthworm.in","r",stdin);
//  freopen("earthworm.out","w",stdout);
    scanf("%lld %lld %lld %lld %lld %lld",&n,&m,&q,&u,&v,&t);
    for(ll i=1; i<=n; i++){
        ll x;
        scanf("%lld",&x);
        Q.push(x);//入队
    }

    for(ll i=1; i<=m; i++){
        ll z=Q.top(); Q.pop();//拿到最大值
        if(i%t==0) printf("%lld ",z);//能整除则输出
        vector<ll> vec;
        while(!Q.empty()){
            vec.push_back(Q.top());
            Q.pop();//取出Q中的所有值
        }
        while(!vec.empty()){
            Q.push(vec.back()+q);//把值+q再反回去
            vec.pop_back();
        }
        ll x=floor(p*z),y=z-x;//拿到值
        Q.push(x); Q.push(y);//入队
    }
    putchar('\n');

    ll i=0;
    while(!Q.empty()){
        i++;
        if(i%t==0) printf("%lld ",Q.top());
        Q.pop();
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

这样会TLE（废话），所以我们要优化

学过线段树的同学会想到lazy mark，这里也可以用类似的方法，延迟更新长度，省了n

这样会有60或65分

如果要有满分，要发现隐含的单调性：先切的对应长度一定比后切的长

用一个单调队列来维护,省了优先队列入队的logn:

q1放原始长度

q2放[p*x]的长度

q3放x-[p*x]的长度

最大值就是三个队列对首的最大值

再说一句：这题会卡常数，所以要用点好玩的，具体见注释

#pragma GCC optimize(2)//常数优化1：O2优化
#include<bits/stdc++.h>
#define ll long long
#define p u*1.0/v
#define INF 2147483647
using namespace std;

ll n,m,q,u,v,t,a[100010];
struct node{
    ll value,Time;
    //长度=value+q*Time
};
queue<node> q1,q2,q3;
inline bool cmp(ll x,ll y){
    return x>y;
}

int main(){
//  freopen("earthworm.in","r",stdin);
//  freopen("earthworm.out","w",stdout);
    scanf("%lld %lld %lld %lld %lld %lld",&n,&m,&q,&u,&v,&t);
    for(ll i=1; i<=n; i++) scanf("%lld",&a[i]);
    sort(a+1,a+1+n,cmp);//排序
    for(ll i=1; i<=n; i++) q1.push(node{a[i],0});//入队

    for(ll i=1; i<=m; i++){
        ll x=-INF;
        if(!q1.empty()) x=max(x,q1.front().value+q*(i-1-q1.front().Time));
        if(!q2.empty()) x=max(x,q2.front().value+q*(i-1-q2.front().Time));
        if(!q3.empty()) x=max(x,q3.front().value+q*(i-1-q3.front().Time));
        //找最大值
        if(!q1.empty()&&q1.front().value+q*(i-1-q1.front().Time)==x) q1.pop();
        else if(!q2.empty()&&q2.front().value+q*(i-1-q2.front().Time)==x) q2.pop();
        else if(!q3.empty()&&q3.front().value+q*(i-1-q3.front().Time)==x) q3.pop();
        //找到最大值对应的队列，并将之出队
        //注意这里一定要有else，否则可能会有多个出列
        //empty应该不会有人忘掉

        if(i%t==0) printf("%lld ",x);//能够整除才输出
        ll y=p*x,z=x-y;//算出两个的长度
        q2.push(node{y,i}); q3.push(node{z,i});//入队
    }
    putchar('\n');//输出换行符

    ll i=0;
    while((!q1.empty())||(!q2.empty())||(!q3.empty())){//三个队列均不为空
        i++;//统计个数
        ll x=-INF;
        if(!q1.empty()) x=max(x,q1.front().value+q*(m-q1.front().Time));
        if(!q2.empty()) x=max(x,q2.front().value+q*(m-q2.front().Time));
        if(!q3.empty()) x=max(x,q3.front().value+q*(m-q3.front().Time));
        if(!q1.empty()&&q1.front().value+q*(m-q1.front().Time)==x) q1.pop();
        else if(!q2.empty()&&q2.front().value+q*(m-q2.front().Time)==x) q2.pop();
        else if(!q3.empty()&&q3.front().value+q*(m-q3.front().Time)==x) q3.pop();
        //与上面同理
        if(i==t){
            printf("%lld ",x);
            i=0;//常数优化2
            //原来是if(i%t==0) printf()
            //LG上能过，但教练的OJ上卡了
            //这样多过几个点
        }
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}