Luogu 2827 [NOIP2016] 蚯蚓

原来真的是按题意模拟啊，还以为有高能的算法可以直接算每个$t$的值。

考虑到先切的蚯蚓一定比后切的蚯蚓长，于是可以弄三个队列分别存放原来的序列和两个切开后的序列，每次取出三个队头的最大值进行扩展。

考虑到每秒钟除了取出来的队头其他的长度都会增加$q$，那么我们可以写一个全局变量$tag$标记现在进行了几轮，然后每一次进队的时候反向减去这一个$tag$就好了。

时间复杂度$O(nlogn)$。

$stl$的$queue$开了$O2$之后就很快了

Code：

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

typedef double db;

const int N = 7e6 + ;

const int inf =  << ;

int n, m, q, t, a[N * ];

db p;

queue <int> Q[];

inline void read(int &X) {

    X = ;

    char ch = ;

    int op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

bool cmp(const int x, const int y) {

    return x > y;

}

inline int bet(int x, int y, int rx, int ry) {

    return rx > ry ? x : y;

}

inline int getQ(int now) {

    if(Q[now].empty()) return -inf;

    else return Q[now].front();

}

inline int getMax() {

    int res[];

    for(int i = ; i < ; i++) res[i] = getQ(i);

    return bet(bet(, , res[], res[]), , res[bet(, , res[], res[])], res[]);

}

int main() {

    int u, v;

    read(n), read(m), read(q), read(u), read(v), read(t);

    p = (db)u / v;

    for(int i = ; i <= n; i++) read(a[i]);

    sort(a + , a +  + n, cmp);

    for(int i = ; i <= n; i++) Q[].push(a[i]);

    int tag = ;

    for(int i = ; i <= m; i++) {

        int now = getMax();

        int z = Q[now].front() + tag;

        Q[now].pop();

        if(i % t == ) printf("%d ", z);

        int x = (int)z * p, y = z - x;

        tag += q;

        x -= tag, y -= tag;

        Q[].push(x), Q[].push(y);

    }

    printf("\n");

    int len = ;

    for(int i = ; i < ; i++)

        for(;!Q[i].empty(); Q[i].pop())

            a[++len] = Q[i].front();

    sort(a + , a +  + len, cmp);

/*    for(int i = 1; i <= len; i++)

        printf("%d ", a[i]);

    printf("\n");   */

    int cnt = (n + m) / t;

    for(int i = ; i <= cnt; i++)

        printf("%d ", a[i * t] + tag);

    printf("\n");

    return ;

}

巴特西

Luogu 2827 [NOIP2016] 蚯蚓

最新文章

热门文章