腾讯笔试部分题解(之后有空可能补题解）

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int solve(vector<pair<int, int>>& vp,int n,int l){
    sort(vp.begin(), vp.end());
    if(vp[0].first!=0) return -1;
    int cnt = 0;
    int pre_end = 0;
    int end = 0;
    for(int i = 0;i<n;){
        while(i<n && vp[i].first <= pre_end){
            end = max(end,vp[i].second);
            i++;
        }
        cnt++;
        pre_end = end;
        if(pre_end>=l){
            return cnt;
        }
    }
    return -1;
}
int main(){
    int n,l;
    scanf("%d %d",&n,&l);
    vector<pair<int, int>> vp(n);
    for(int i = 0;i<n;i++){
        scanf("%d %d",&vp[i].first,&vp[i].second);
    }
    cout<<solve(vp, n, l)<<endl;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> v(n,0);
    for(int i = 0;i<n;i++){
        scanf("%d",&v[i]);
    }
    stack<int> st1;
    stack<int> st2;
    vector<int> left(n,0);
    vector<int> right(n,0);
    vector<int> z(n,0);
    for(int i = 0;i<n;i++){
        if(st1.empty()||st1.top()>v[i]){
            left[i] = st1.size();
            st1.push(v[i]);
        }else{
            left[i] = st1.size();
            while(!st1.empty() && v[i]>=st1.top()){
                st1.pop();
            }
            st1.push(v[i]);
        }
    }
    for(int i = n-1;i>=0;i--){
        if(st2.empty() || st2.top()>v[i]){
            right[i] = st2.size();
            st2.push(v[i]);
        }else{
            right[i] = st2.size();
            while(!st2.empty() && st2.top()<=v[i]){
                st2.pop();
            }
            st2.push(v[i]);
        }
    }
    for(int i = 0;i<n;i++){
        cout<<left[i]+right[i]+1<<" ";
    }
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> v1(n);
    vector<int> v2(n);
    for(int i = 0;i<n;i++) scanf("%d",&v1[i]);
    for(int i = 0;i<n;i++) scanf("%d",&v2[i]);
    int dp[n+1][2];
    memset(dp, 0, sizeof dp);
    for(int i = 0;i<n;i++){
        if(v1[i]==1){
            dp[i+1][0] = (i<1?0:dp[i-1][0])+1;
            if(i-1>0 && v1[i-1]==0) dp[i+1][0] = max(dp[i+1][0],dp[i][0]+1);
            dp[i+1][0] = max(dp[i+1][0],dp[i][1]+1);
        }else if(v1[i]==0){
            dp[i+1][0] = max(dp[i+1][0],dp[i][0]);
            dp[i+1][0] = max(dp[i+1][0],dp[i][1]);
        }
        if(v2[i]==1){
            dp[i+1][1] = (i<1?0:dp[i-1][1])+1;
            if(i-1>0 && v2[i-1]==0) dp[i+1][1] = max(dp[i+1][1],dp[i][1]+1);
            dp[i+1][1] = max(dp[i+1][1],dp[i][0]+1);
        }else if(v2[i]==0){
            dp[i+1][1] = max(dp[i+1][1],dp[i][1]);
            dp[i+1][1] = max(dp[i+1][1],dp[i][1]);
        }
    }
    cout<<n-max(dp[n][0],dp[n][1])<<endl;
}