洛谷2827 蚯蚓

本文于 2019.10.17 被重写。


Luogu

分析

首先我们是没有必要每次给所有蚯蚓加 $q$ 的,只需要维护一个变量 add 表示所有蚯蚓长了多少即可。

那么一个显然的想法是用一个大根堆维护所有蚯蚓,然后直接模拟一下就好了。这样子就有 $85$ 分了。

注意到每次分出去的蚯蚓一定会成为最短的两条蚯蚓(想一想,为什么?),那么只需要开三个队列维护就好了。

注意一下输入进来的长度没有排好序,自己要排一下。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,q,t; double p;
int a[N];
queue<int> Q[3];
int add=0;

inline int getmax() {
    int res=-2e9,resp=0;
    for (re int i=0;i<3;++i)
        if (!Q[i].empty()&&Q[i].front()>res) res=Q[i].front(),resp=i;
    Q[resp].pop(); return res;
}

int main() {
    n=read(),m=read(),q=read(),p=1.0*read()/read(),t=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+n+1);
    for (re int i=n;i;--i) Q[0].push(a[i]);
    for (re int i=1;i<=m;++i) {
        int x=getmax()+add;
        if (i%t==0) printf("%d ",x);
        int l=p*x,r=x-l; add+=q;
        Q[1].push(l-add),Q[2].push(r-add);
    }
    puts("");
    for (re int i=1;i<=n+m;++i) {
        int x=getmax()+add;
        if (i%t==0) printf("%d ",x);
    }
    puts("");
    return 0;
}
最后修改:2019 年 10 月 17 日 02 : 19 PM

发表评论