专栏首页数据结构与算法洛谷P2827 蚯蚓(单调队列)

洛谷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 + 10, INF = 1e9 + 10;
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, All, T, u, v, a[MAXN], p;
queue<int> q[3];
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 = 1; i <= N; i++) a[i] = read();
    sort(a + 1, a + N + 1, comp);
    for(int i = 1; i <= N; i++) q[0].push(a[i]);
    int cur = 0;
    for(int i = 1; i <= M; i++) {
        //if(i == 5) {printf("%d ", q[2].front());}
        int val = -INF, mx = 0;
        for(int j = 0; j < 3; 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[1].push(1ll * (top + cur) * u / v - cur - All);
        q[2].push((top + cur) - 1ll * (top + cur) * u / v - cur - All);
        
        cur += All;
    }
    puts("");
    priority_queue<int> ans;
    for(int i = 1; i <= N + M; i++) {
        int val = -INF, mx =0 ;
        for(int j = 0; j < 3; 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 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • cf914D. Bash and a Tough Math Puzzle(线段树)

    可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。

    attack
  • P1807 最长路_NOI导刊2010提高(07)

    题目描述 设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当为G中的一条边时有i < j。设w(i,j)为边的长度,请设计算法,计算图G中<1,n>间...

    attack
  • P3371 【模板】单源最短路径

    题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。 输入输出格式 输入格式: 第一行包含三个整数N、M、S,分别表示点的个数、有...

    attack
  • cf914D. Bash and a Tough Math Puzzle(线段树)

    可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。

    attack
  • HDU4031(树状数组)详解

    逐梦的青春
  • BZOJ2683: 简单题(cdq分治 树状数组)

    你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:

    attack
  • 团体程序设计天梯赛-练习集 L1-028 判断素数

    输入在第一行给出一个正整数N(≤ 10),随后N行,每行给出一个小于231的需要判断的正整数。

    C you again 的博客
  • POJ 2236 Wireless Network(并查集裸题)

           题意是发生了地震把电脑都震坏了,然后要修复这些电脑,先输入n,d,表示有编号为1-n的这么多电脑,d表示两台电脑的距离不大于d时可以连接,然后输入...

    Ch_Zaqdt
  • POJ 1679 The Unique MST(Kruskal+记录边)

           首先我们求一个最小生成树把每条边记录下来,然后我们对这个最小生成树进行删边操作,再删除一条边后,能不能再生成一个权值相同的最小生成树就行了。我刚开...

    Ch_Zaqdt
  • Python Tips(1) 数字与字符串之间转换,采用内置函数

    glm233

扫码关注云+社区

领取腾讯云代金券