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

最大数组和

在这里插入图片描述

算法思路：利用前缀和化简 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;
}