2025牛客寒假训练营1-M题

登录—专业IT笔试面试备考平台_牛客网

题目是翻倍一个连续子区间内的所有元素,求最大值和最小值的最小差。
那么最先的思路肯定是从最小值开始翻倍,然后是次小值,因为如果不翻倍最小值所在区间,那么次小值即使翻倍了只可能增大最大值,而不可能增大最小值。
因为区间是连续的,我们也不可能选完最小值然后就接着选择次小值,很有可能在最小值到次小值所在区间内,最大值也在里面。那么我们不妨枚举每一个数,假设它是我们最后要翻倍的区间的最大值,这个区间是连续的,符合二叉树的性质,这个区间内的所有值都比它要小,这符合堆的性质,这两个性质结合其它其实就是笛卡尔树.

constexpr int inf = 2E9;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}int ans = inf;std::vector<int> pmin(n + 1), pmax(n + 1), smin(n + 1), smax(n + 1);pmin[0] = smin[n] = inf;for (int i = 0; i < n; i++) {pmin[i + 1] = std::min(pmin[i], a[i]);pmax[i + 1] = std::max(pmax[i], a[i]);}for (int i = n - 1; i >= 0; i--) {smin[i] = std::min(smin[i + 1], a[i]);smax[i] = std::max(smax[i + 1], a[i]);}std::vector<int> stk;std::vector<int> lc(n, -1), rc(n, -1);for (int i = 0; i < n; i++) {while (!stk.empty() && a[i] > a[stk.back()]) {int x = stk.back();rc[x] = lc[i];lc[i] = x;stk.pop_back();}stk.push_back(i);}while (stk.size() > 1) {int x = stk.back();stk.pop_back();rc[stk.back()] = x;}auto dfs = [&](auto &&self, int x, int l, int r) -> int {if (x == -1) {return inf;}int mn = std::min({self(self, lc[x], l, x), self(self, rc[x], x + 1, r), a[x]});int min = std::min({mn * 2, pmin[l], smin[r]});int max = std::max({a[x] * 2, pmax[l], smax[r]});ans = std::min(ans, max - min);return mn;};dfs(dfs, stk[0], 0, n);std::cout << ans << "\n";return 0;
}

pmin就是i左边的最小值,pmax就是最大值,同理smin和smax就是最大值,求完这些以后我们建立一个笛卡尔树.

这是一颗大根堆笛卡尔树的结构,第一个值是下标,第二个就是值,可以发现叶子节点就是要么它左边一个比它小,要么它右边一个比它小 .

dfs里做了一件什么呢?首先一直递归到叶子节点,叶子节点的mn就是它本身,因为再向下递归返回是inf,再然后到某个根节点,它的mn肯定是左边和右边连续比它小的所有值的最小值.
举个例子比如在8这个根节点,一直往左看,第一个3比它小那么肯定属于8所在区间,6比它小,5比它小也属于它所在区间,但是往右看9比它大,那么就不属于8所在区间,因为如果要往右再去找的话9就会被翻倍,所以8就不再是这个连续区间的最大值了.

然后mn属于这个区间的最小值,a[x]属于这个区间的最大值,pmin[l]和smin[r]就是除去这个区间后的最小值,然后和2*mn(因为我们选这个区间就是要翻倍的嘛,所以要乘2)取个min,同理求出max,然后更新我们的ans.

重新理一下思路:我们选择一个数,把它作为要翻倍的连续区间的最大值,然后找到这个连续区间内的最小值,然后更新答案.所以时间复杂度是On.