洛谷P2827 蚯蚓(单调队列)

题意

初始时有$n$个蚯蚓，每个长度为$a[i]$

有$m$个时间，每个时间点找出长度最大的蚯蚓，把它切成两段，分别为$a[i] * p$和$a[i] - a[i] * p$，除这两段外其他的长度都加一个定值$q$。

每次询问被蚯蚓被切前的长度

Sol

用堆模拟可获得$50 - 85$不等的分数。

蚯蚓的长度有单调性。然后这题就做完了。。。

首先把$a[i]$排序

我们分别维护三个数组$a, b, c$，分别表示未被切的蚯蚓，被切成$p * a[i]$的蚯蚓和被切成$a[i] - p * a[i]$的蚯蚓

然后每次取出这三个里面最大的，切开之后再插回去就行了

大概口胡一下单调性的证明：

这题中最重要的两个条件是$a_i$有序以及$0 < p < 1$

首先$a_i$有单调性是显然的

考虑$b, c$中的元素一定是按照从小到大的顺序加入的，且不受全局标记的影响。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

const int MAXN = 1e7 + , INF = 1e9 + ;

using namespace std;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, M, All, T, u, v, a[MAXN], p;

queue<int> q[];

bool comp(const int &a, const int &b) {

    return a > b;

}

int main() {

    N = read(); M = read(); All = read(); u = read(); v = read(); T = read(); p = u / v;

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

    sort(a + , a + N + , comp);

    for(int i = ; i <= N; i++) q[].push(a[i]);

    int cur = ;

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

        //if(i == 5) {printf("%d ", q[2].front());}

        int val = -INF, mx = ;

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

            if(!q[j].empty() && q[j].front() > val) mx = j, val = q[j].front();

        int top = val; q[mx].pop();

        if(!(i % T)) printf("%d ", val + cur);

        q[].push(1ll * (top + cur) * u / v - cur - All);

        q[].push((top + cur) - 1ll * (top + cur) * u / v - cur - All);

        cur += All;

    }

    puts("");

    priority_queue<int> ans;

    for(int i = ; i <= N + M; i++) {

        int val = -INF, mx = ;

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

            if(!q[j].empty() && q[j].front() > val) mx = j, val = q[j].front();

        q[mx].pop();

        if(!(i % T))

            printf("%d ", val + cur);

    }

    return ;

}

巴特西

洛谷P2827 蚯蚓(单调队列)

题意

Sol

最新文章

热门文章