当前位置：首页 > news >正文

蓝桥杯倒计时 43天 - 前缀和，单调栈

news 来源：原创 2024/6/5 22:39:55

最大数组和

在这里插入图片描述

算法思路：利用前缀和化简 for 循环将 n^2 简化成 n+n，以空间换时间。枚举每个 m，m是删除最小两个数，那k-m就是删除最大数，m<=k，求和最大的值。暴力就是枚举 m-O(n)，计算前 n-(k-m)的和减去前 2*m 的和O(n+n)。前缀和能化简求前 n 个和的过程变成 O(1)的复杂度，因为前缀和能够直接进行直接查询。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5+10;LL a[N];
int t,n,k;
LL sum[N];int main( ){cin>>t;while(t--){memset(a, 0, sizeof(a));memset(sum, 0, sizeof(sum));cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n;i++)sum[i]=a[i]+sum[i-1];LL ans = 0;for(int m=0;m<=k;m++){ans = max(ans,sum[n-(k-m)]-sum[2*m]);}cout<<ans<<endl;}return 0;
}

可以利用 vector 化简代码，不过数组下标要从 0开始。

视野总和

描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2

思路：设置单调递减栈，复杂度 On，如果暴力，复杂度 On^2

#include<bits/stdc++.h>
using namespace std;
stack<int> st;
const int N = 1e5 +10;
int n;
int a[N];
int main( ){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int ans = 0;for(int i=1;i<=n;i++){if(st.empty()||st.top()>=a[i])st.push(a[i]);else{while(!st.empty()&&st.top()<a[i]){st.pop();ans++;}st.push(a[i]);if(st.empty())ans--;}}cout<<ans<<endl;return 0;
}

柱状图中的最大矩形

柱状图中的最大矩形
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 +10;
int n;
int a[N];
vector<int> heights;
int main( ){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int ans = 0;for(int i=1;i<=n;i++){int wide=1;for(int j=i-1;j>=1;j--){if(a[j]>=a[i])wide++;}for(int j=i+1;j<=n;j++){if(a[j]>=a[i])wide++;}ans = max(ans,wide*a[i]);}cout<<ans<<'\n';return 0;
}

四元组问题

在这里插入图片描述

青茶绿梅*2博主讲的很好

暴力做法 n^4 能过 50%，所以需要进行优化，这题需要 n 或 nlogn 的时间复杂度。
算法思路：将四元组问题转化成三元组（单调递减栈）+前缀和问题。假设前三个元素已经知道，那只需要找到小于 c 的 d 则四元组存在，利用后缀和来得到c后面的最小值作为 d。然后找前三元组，前三元组的 abc 的曲线画出来有利于理解。算法思路：将一个元素入栈，然后从左到右依次与栈顶判断，如果小于栈顶入栈，如果大于栈顶，则出栈直到小于栈顶或栈元素为空，这时，最后一个出栈的为 a，入栈元素为 b，如果接下来继续操作，找到比栈顶元素大，则继续刚才过程，同时更细 a 与 b，如果找到比栈顶元素小，则为 c 可以查询后缀和判断是否有 d 的存在。栈顶元素是目前最大的 b。
模拟一下：1000 333 222 888 999 100 50

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 +10;
int n;
int nums[N];
stack<int> st;
int main( ){cin>>n;for(int i=1;i<=n;i++)cin>>nums[i];int k=INT_MIN;vector<int>min_r(n,INT_MAX);for (int i=n-1; i>=1; i--) {min_r[i] = min(min_r[i+1],nums[i]);}for(int i=1;i<=n;i++){if(k>nums[i]&&nums[i]>min_r[i]){cout<<"YES";return 0;}while(!st.empty()&&st.top()<nums[i]){k = max(k,nums[i]);st.pop();}st.push(nums[i]);}cout<<"NO";return 0;
}