本文主要是介绍两点问题 模型,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
这个模型。。我不知道专业的是怎么称呼。。我叫他两点问题。。
lc的两数之和。。就是这个模型的经典。。
他适用于连续区间的统计问题。点对问题计数。树上也行。甚至可以用在回文区间统计。(由内而外的枚举)
因为点对问题 很常见。。这种思想的应用就很广泛。。
他的暴力是n^2 .一般都能优化成n*logn
原理就是枚举右端点。。然后我们通过数据结构的预处理 可以快速的拿到 左端点的有效个数。。
、以后会记录一些经典的场景吧。。。题目
下面记录一种看似和两点问题没有任何关系。但是模式上非常像
for (int i = 1; i <= n; ++i) {ans = max(ans, pre + mx[i]);pre += sum[i];}//就是sum[1]+sum[2]+sum[3]。。。然后求这之前前缀最大的一个位置?// 这个实际上也类似两点问题。。的拓展。。。//🦋枚举整点的。。快速获得零散的最优值//和两点问题 枚举右端点 快速获取左端点的最优值 多么相似。
这篇关于两点问题 模型的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!