P1873 [COCI 2011/2012
思路分析典型的二分答案问题。求满足条件的最大高度,用开区间二分模板。 在输入时记录树的最大高度作为二分右边界 check(mid):遍历所有树,计算以 mid 高度砍树能获得的木材总长 如果木材足够(>= M),说明高度还能抬高,左边界右移;否则右边界左移 最后输出左边界(包含了等于 M 的情况) 高度越低,砍到的木材越多;高度越高,木材越少。 代码实现12345678910111213int l = -1, r = highest + 1;while (l + 1 < r) { int mid = (l + r) / 2; if (check(arr, M, mid)) l = mid; else r = mid;}System.out.println(l);static boolean check(int[] q, int m, int x) { long sum = 0; for (int h : q) sum += Math.max(0, h - x); return sum >= m...
Queries on a String
思路分析直接按题意模拟字符串的每次移位操作会超时。 优化思路:对于任何一个位置的字符,它经过一次区间轮转后的新位置是确定的。可以用一个数组记录每个字符最终的位置,避免真的去移动字符。 公式:字符的最终位置 = (当前位置 + 旋转次数) % 区间长度 + 区间起点 小结 字符串轮转类问题,直接模拟往往不是最优解 可以用数学方式直接算出最终位置,避免逐次移动
Run For Your Prize
思路分析两个人分别在位置 1 和位置 10^6,速度相同,要去拾取若干礼物。 每个礼物谁离得更近就由谁去捡(因为速度相同),然后更新该人的位置。 把路程对半分: 礼物坐标 < 500000 → 左边的人去捡 礼物坐标 >= 500000 → 右边的人去捡 最终时间是两边各自最远距离的最大值。 小结 把问题拆成左右两半,分别独立计算 最终时间 = max(左边最远距离, 右边最远距离)
Hello World,我的第一篇博客
欢迎来到我的博客!这是一篇基于主流 Hexo 语法的演示文章,展示了各种排版效果。 1. 文字排版这是一段普通的文本。你可以使用 粗体 来强调重点,或者使用 斜体 表示专有名词。如果你需要标记被废弃的内容,可以使用 删除线。 2. 引用与标注 技术是一门艺术,而代码是我们的画笔。—— 某程序员 3. 代码展示行内代码示例:你可以通过 npm install 来安装依赖。 多行代码块: 12345678910// 这是一个简单的防抖函数function debounce(func, wait) { let timeout; return function() { clearTimeout(timeout); timeout = setTimeout(() => { func.apply(this, arguments); }, wait); };} 4. 数据表格 框架/工具 核心优势 适用场景 Hexo 静态生...
