【问题】一个关于最优子区间的求解问题

子区间均值最大？ 没看懂你表述的意思 不过桶排序的思想你可以借鉴一下

把所有n个点离散化后从左往右标号为1-n，d[i]为标号为i的点在原来坐标中的位置 假设选取的区间为(L,R]，即选择了第L+1个点到第R个点作为答案区间 那有ans = (R - L) * (R - L) / (d[R] - d[L])，考虑二分答案k，然后考虑judge函数 从左向右枚举选择的区间的右端点r,那么固定右端点r，我们需要找到合适的l 使得(r - l) * (r - l) / (d[r] - d[l]) >= k， 如果能够找到合适的l，就意味着最终ans>=k 移项处理一下得到 min(k * d[r] - r * r - k * d[l] - l * l + 2 * r * l) <= 0 因为枚举过程中右端点是固定的，所以就是使得 min(- k * d[l] - l * l + 2 * r * l) <= r * r - k * d[r] 令f(i) = -k * d[i] - i * i + 2 * i * r， 我们需要在从左向右枚举r的过程中 维护 min(f(i), 1 <= i < r), 考虑f(i)的性质会发现，对于j < k，在r增大的过程中 f(j)与f(k)的大小关系要么是一直有f(j) < f(k),要么就是先>后<，要么就是一直> 考虑清楚这个性质之后可以考虑用链表+堆中维护，总复杂度O(n*(logn)^2),n为点数 链表中相邻两个元素j,k意味着在当前r下, f(j) > f(k) 并且对于j < i < k, 都有f(j) < f(i) 然后可以直接计算出当r达到多少时会出现f(j) <= f(k) 假设当r=t时会首次出现f(j) <= f(k) 就把(j, k, t)塞入以t为key的小根堆中 然后每次枚举新的r时就while检查堆顶元素是否满足t<=r,满足则pop 检查该元素中的j是否已被删去，已被删去直接continue 否则在链表中去掉k，如果链表中k后面有元素p 则重新计算新值new_t，并将(j, p, new_t)塞入堆中 检查结束之后，链表最后一个元素就是我们在当前r下需要的l了 总感觉这么维护有点子复杂...暂时没有想到简单维护方法