html手机网站模板下载,免费的会计做账系统,官方制作网站,物流网站建设模板登录—专业IT笔试面试备考平台_牛客网
题目是翻倍一个连续子区间内的所有元素,求最大值和最小值的最小差。 那么最先的思路肯定是从最小值开始翻倍,然后是次小值,因为如果不翻倍最小值所在区间,那么次小值即使翻倍了只可能增大最大值,而不可能增大最小值。 因为区间是连续的,我…登录—专业IT笔试面试备考平台_牛客网
题目是翻倍一个连续子区间内的所有元素,求最大值和最小值的最小差。 那么最先的思路肯定是从最小值开始翻倍,然后是次小值,因为如果不翻倍最小值所在区间,那么次小值即使翻倍了只可能增大最大值,而不可能增大最小值。 因为区间是连续的,我们也不可能选完最小值然后就接着选择次小值,很有可能在最小值到次小值所在区间内,最大值也在里面。那么我们不妨枚举每一个数,假设它是我们最后要翻倍的区间的最大值,这个区间是连续的,符合二叉树的性质,这个区间内的所有值都比它要小,这符合堆的性质,这两个性质结合其它其实就是笛卡尔树.
constexpr int inf 2E9;int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n;std::cin n;std::vectorint a(n);for (int i 0; i n; i) {std::cin a[i];}int ans inf;std::vectorint 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::vectorint stk;std::vectorint 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.
