CSUST 上场最简单题 题解（线段树）

题目链接

题目大意

从左到右选三道题，要求难度递增，求花费时间的最小值。

题目思路

emm，对于这种题目，看到三个值，其实就想要枚举中间值，然后这个又是类似于逆序对。
以难度值为节点编号 ，时间为节点值，然后边找边更新，左右都来一次就好了。

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define min minn
#define debug printf(" I am here\n");
using namespace std;
typedef long long ll;
typedef pair<int,pair<int,int> > pii;
const int maxn=1e6+5,mod=998244353,inf=0x3f3f3f3f;
const double eps=1e-10;
int n,a[maxn],b[maxn],tree[maxn<<2],ri[maxn],le[maxn];
inline int min(int a,int b){
    return a>b?b:a;
}
int query(int node,int L,int R,int l,int r){
    if(L<=l&&r<=R){
        return tree[node];
    }
    if(l>=r){
        return inf;
    }
    int mi=inf,mid=(l+r)>>1;
    if(mid>=L) mi=min(mi,query(node<<1,L,R,l,mid));
    if(mid<R) mi=min(mi,query(node<<1|1,L,R,mid+1,r));
    return mi;
}
void update(int node,int pos,int num,int l,int r){
    if(l==r){
        tree[node]=min(tree[node],num);
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=pos) update(node<<1,pos,num,l,mid);
    else    update(node<<1|1,pos,num,mid+1,r);
    tree[node]=min(tree[node<<1],tree[node<<1|1]);
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
    }
    memset(tree,0x3f,sizeof(tree));
    for(int i=1;i<=n;i++){
        le[i]=query(1,1,a[i]-1,1,1e6);
        update(1,a[i],b[i],1,1e6);
    }
    memset(tree,0x3f,sizeof(tree));
    for(int i=n;i>=1;i--){
        ri[i]=query(1,a[i]+1,1e6,1,1e6);
        update(1,a[i],b[i],1,1e6);
    }
    int ans=inf;
    for(int i=1;i<=n;i++){
        ans=min(ans,ri[i]+le[i]+b[i]);
    }
    if(ans==inf){
        printf("-1\n");
    }else{
        printf("%d\n",ans);
    }
    return 0;
}

本文地址：https://blog.csdn.net/m0_46209312/article/details/107614233