最远专题

力扣1642.可以到达的最远建筑

力扣1642.可以到达的最远建筑二分答案 class Solution {public:int furthestBuilding(vector<int>& heights, int bricks, int ladders) {auto check = [&](int mid) -> bool{vector<int> h;for(int i=1;i<=mid;i++){int t = h

CF 366E - Dima and Magic Guitar 最远曼哈顿距离

题目：http://codeforces.com/problemset/problem/366/E 其实就是找 n * m 矩阵中数字 x 和数字 y 的最远距离。方法参照武森的论文《浅谈信息学中的“0”和“1”》先约定符号：xi,xj (i,j)是x的下标，当然，矩阵中的值是可以重复的上面是武森的论文原文，加上我之前的符号约定，我在做点解释：其实那个max={四种可能

离线缓存问题的最优解决方案——将来最远策略

离线缓存问题的最优解决方案——将来最远策略 a. 将来最远策略的缓存管理器伪代码及运行时间分析b. 离线缓存问题的最优子结构性质证明c. 将来最远策略的最优性证明及示例在现代计算机系统中，缓存技术是提高数据处理速度的关键。通过将主存中的少量数据保存在容量小但速度更快的缓存(cache)内存中，可以显著降低数据访问时间。然而，当缓存容量有限时，必须精心选择哪些数据保留在缓存中，以最

POJ 2187 Beauty Contest (凸包最远点距旋转卡壳)

http://poj.org/problem?id=2187 思路：算出凸包后枚举凸包上的点。复杂度为O(NlogN+M) 为什么可以枚举？设坐标的绝对值不超过M，则凸包至多有O(√M)个顶点证明：以(0,0)为起点画出如下“极限凸包” (0,0)-(1,0)-(2,1)-(3,3)-(4,6)-...当x每次只增加1时，y增加速率是平方级的，所以凸包至多有O(√M)个顶点。

【leetcode C++】1642. 可以到达的最远建筑 1642. Furthest Building You Can Reach

1642. 可以到达的最远建筑 1642. Furthest Building You Can Reach class Solution {public:int furthestBuilding(vector<int>& heights, int bricks, int ladders) {priority_queue<int, vector<int>, greater<int> > PQ

[树上DP] POJ2631 树的最长路径（最远点对）

题目对于一棵n个结点的无根树，找到一条最长路径。换句话说，要找到两个点，使得它们的距离最远。 POJ2631 思路和树的重心问题一样，先把无根树转成有根树。对于任意结点i，经过i的最长路就连接i的两棵不同子树u和v的最深叶子的路径。基本的求法是，先随便找一个点作为根结点转换为无根树后，遍历每一个点，找出当i为根结点时的子树到叶子的最大距离d(j)，在根据d(j)求出结点i作为根

基于paddlepaddle的FPS最远点采样

什么是FPS最远点采样？最远点采样（Farthest Point Sampling，FPS）是一种常用的采样算法，主要用于点云数据（如激光雷达点云数据、分子坐标等）的采样。为了方便解释，定义一下待采样点到采样点的“距离”为待采样点到所有采样点的距离的最小值。这种算法的核心思想是，一开始先从数据集中随机采样一个点，然后采样距离采样点最远的待采样点作为下一个采样点，以此类推，直到达到所需的

以45°斜抛水平距离最远

已知：斜抛物体的初速度为 v 0 v_0 v0（与水平方向的夹角为 θ \theta θ），重力加速度为 g g g。求：抛物轨迹方程？垂直方向的速度为 v y = v 0 sin ⁡ θ − g t v_y=v_0 \sin \theta -gt vy=v0sinθ−gt 水平方向的速度为 v x = v 0 cos ⁡ θ v_x=v_0 \cos \theta v

树的直径（两次最远法）

原题链接树中的最长路径称为树的直径。一棵树可以有多条直径，他们的长度相等。两次最远法步骤：任取一个结点 u u u，找出树中距 u u u最远的结点，记为 v v v再以 v v v作为起点，找出树中距 v v v最远的结点，记为 w w w则 v , w v,w v,w之间的距离即树的直径显然，如果 v v v是直径的一端，那么距其最远的结点 w w w 一定是直径

POJ 2187 Beauty Contest (旋转卡壳最远点对)

http://poj.org/problem?id=2187 题意：给出二维平面上n个点的坐标，求距离最远的点对距离的平方。显然距离最远的两个点在这些散点的凸包上，然后用旋转卡壳的算法找出最远点对，具体原理参见这位大佬的博客http://www.cnblogs.com/xdruid/archive/2012/07/01/2572303.html 大概是利用凸包上的点依次与对应边产生的距离成

通俗描述，带图，最远点采样法FPS(Farthest Point Sampling)

另一个描述: https://www.it610.com/article/1279200974338015232.htm 我自己对算法的描述：每一次都选最远的点加入进来，这样能够使得所选的点足够分散并覆盖全部。所以关键在于每次都要选最远的点。 1. 第一个点可以随便初始化 2. 第二点选最远的点 3. 第三个点该怎么选呢? 当然也是要选离第一个和第二个点都最远的点。我们

innovus：报告到clock root物理距离最远的sink

我正在「拾陆楼」和朋友们讨论有趣的话题，你⼀起来吧？拾陆楼知识星球入口分析clock tree的时候可以看到一些delay detour buffer，其作用是为了满足balance的要求不得已去垫delay，在版图上兜兜绕绕的插buffer，这时候分析就需要找到把它们拉长的原因，单纯分析latency最到的部分sink未必能找到原因，而找到距离root最远的sink也有很高的参考价