【Leetcode单调队列】- 洛谷P1714切蛋糕
发布日期:2021-06-29 15:36:23
浏览次数:2
分类:技术文章
本文共 909 字,大约阅读时间需要 3 分钟。
单调队列
解决该类问题的重点维护一个队列,从队首到队尾是递减的,队首是最大的。队尾是最小的。
队尾接受值,队首排出值。
Java实现用双端队列,前面接收值,后面排出来值。
这类题目往往是跟滑动窗口一起出现的,在滑动窗口K的范围内查找最大最小值。
2.洛谷P1714切蛋糕
今天是小Z的生日,同学们为他带来了一块蛋糕。这块蛋糕是一个长方体,被用不同色彩分成了N个相同的小块,每小块都有对应的幸运值。
小Z作为寿星,自然希望吃到的第一块蛋糕的幸运值总和最大,但小Z最多又只能吃M小块(M≤N)的蛋糕。
吃东西自然就不想思考了,于是小Z把这个任务扔给了学OI的你,请你帮他从这N小块中找出连续的k块蛋糕(k≤M),使得其上的幸运值最大。
输入格式
输入文件cake.in的第一行是两个整数N,M。分别代表共有N小块蛋糕,小Z最多只能吃M小块。
第二行用空格隔开的N个整数,第i个整数Pi代表第i小块蛋糕的幸运值。
输出格式
输出文件cake.out只有一行,一个整数,为小Z能够得到的最大幸运值。
输入输出样例
输入 #1复制
5 21 2 3 4 5
输出 #1复制
9
输入 #2复制
6 31 -2 3 -4 5 -6
输出 #2复制
5
维护一个最小的值;在单调队列中,队首最小,队首到队尾单调递增
import java.util.*; class Main{ // 主函数public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[] pre = new int[n]; // 前缀数组 for(int i=0;iqueue = new LinkedList<>(); int res = Integer.MIN_VALUE; // 滑动窗口 里面维护的一个最小的 即队首到队尾是递增的 队首是最小的 for(int i=0;i
转载地址:https://codingchaozhang.blog.csdn.net/article/details/115801654 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月27日 11时08分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
IDEA 怎么删除一个Module
2019-04-29
JAVA 和MySQL使用JDBC连接
2019-04-29
JAVA 反射的性能测试
2019-04-29
HTML 初探
2019-04-29
成功关键在于此:如何创造一个有即时价值的最小化可行产品?
2019-04-29
终端大改造:只需五步,构建你的梦中情“端”
2019-04-29
你的代码“balance”怎么样?找到简洁性和可读性的平衡点
2019-04-29
中科院刘康:低资源环境下的事件知识抽取
2019-04-29
提高软件工程技能的关键技术,这些资源赶紧收藏起来
2019-04-29
走进数据科学:最好是通过比网课更好的方法
2019-04-29
机器学习背后的数学支柱,这5本书帮你搞定!
2019-04-29
AI革命第一步:最容易被忽略但必不可少的物联网
2019-04-29
2020年开发运维工具清单:选择开发运维工具堆栈吧
2019-04-29
效率提升法则:高效人士不会去做的4件事
2019-04-29
8.PostgreSQL约束
2019-04-29
【技术分享】使用AES加密技术保障数据安全
2019-04-29
【应用实例】布线多?成本高?不可靠?泽耀方案没烦恼!
2019-04-29
数据可视化工具:Matplotlib绘图
2019-04-29
用Python写个超级小恐龙跑酷游戏,上班摸鱼我能玩一天
2019-04-29
闺蜜看我用Python画了一幅樱花图,吵着要我给他介绍程序员小哥哥
2019-04-29