洛谷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 条评论
登录 后参与评论

相关文章

来自专栏androidBlog

HashMap及HashTable源码解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

8710
来自专栏用户画像

4.5.3 哈弗曼树(Huffman)树和哈弗曼编码

树中结点被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的...

8210
来自专栏WD学习记录

Python数据结构与算法笔记(4)

前序遍历中,我们首先访问根节点,然后递归地做左侧子树的前序遍历,随后是右侧子树的递归前序。

13120
来自专栏小灰灰

JDK容器学习之TreeMap (一) : 底层数据结构

TreeMap 在日常的工作中,相比较与HashMap而言,TreeMap的使用会少很多,即使在某些场景,需要使用到排序的Map时,也更多的是选择 Linke...

27190
来自专栏小樱的经验随笔

51 Nod 1008 N的阶乘 mod P【Java大数乱搞】

1008 N的阶乘 mod P 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 输入N和P(P为质数),求N! Mod P ...

28660
来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

381110
来自专栏包子铺里聊IT

How to find the lowest common ancestor in a tree 最近公共祖先

[题目] 求二叉树的任意两个节点的最近公共祖先。 此题有多个扩展问题: 如果只查询一次,二叉树给出向上(parent)链接和不给向上链接时分别有什么解法,最佳空...

28340
来自专栏移动端开发

用OC和Swift一起说说二叉树

   一:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)...

10850
来自专栏移动端开发

用OC和Swift一起说说二叉树

前言:    一:在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subt...

25050
来自专栏数据结构与算法

P1040 加分二叉树

题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节...

333100

扫码关注云+社区

领取腾讯云代金券