关于lowerbound求助
查看原帖
关于lowerbound求助
1169369
Gusare楼主2024/11/12 19:18

求教
为什么把下面的

lower_bound(st.begin(),st.end(),x)

改成

st.lower_bound(x)

就不会tle了
下面是我的 tle 40 pts代码

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;

ll n,x,ans;
set<ll> st;
void solve();

void solve(){
    cin>>n>>ans;
    st.insert(-inf);
    st.insert(inf);
    st.insert(ans);
    for(ll i=1;i<=n-1;i++){
        cin>>x;
        auto it=lower_bound(st.begin(),st.end(),x);
        ll a=*it;
        ll b=*prev(it);

        // cerr<<a<<' '<<b<<'\n';

        ans+=min(abs(a-x),abs(b-x));
        st.insert(x);
    }
    cout<<ans<<'\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
2024/11/12 19:18
加载中...