gpt4 book ai didi

c++ - set.upper_bound()和upper_bound(set.begin(),set.end())STL之间的区别

转载 作者:行者123 更新时间:2023-12-03 07:09:43 31 4
gpt4 key购买 nike

https://codeforces.com/contest/1435/submission/96757666->使用set.upper_bound()
https://codeforces.com/contest/1435/submission/96761788->使用upper_bound(set.begin(),set.end())
我注意到set.upper_bound()比后者快(后者给出了超过时间限制)。这是为什么?
下面的代码给出了超过时间限制

int ind = *upper_bound(st.begin(), st.end(), mp[i], greater< int >());

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
# define ld long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
int n;
cin>>n;
set<int, greater<int>>st;
st.insert(-1);
map<int,int> mp;
int p[2*n];
char s[2*n];
for(int i=0;i<2*n;i++)
{
cin>>s[i];
if(s[i]=='+')
st.insert(i);
else
{
cin>>p[i];
mp[p[i]]=i;
}

}
for(int i=1;i<=n;i++)
{

int ind = *upper_bound(st.begin(), st.end(), mp[i], greater< int>());
if(ind==-1||st.find(ind)==st.end())
{
// if (-) come before +
cout<<"NO\n";
return;
}
st.erase(ind);
p[ind] = i;

}

// cout<<endl;
stack<int>stc;
for(int i=0;i<2*n;i++)
{
if(s[i]=='+')
stc.push(p[i]);
else
{
if(stc.top()==p[i])
stc.pop();
else
{
//if element not in order given in language
cout<<"NO\n";
return ;
}
}
}
cout<<"YES\n";
for(int i=0;i<2*n;i++)
{
if(s[i]=='+')
cout<<p[i]<<endl;
}
return;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
IOS
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
具有“set.upper_bound()”的相同代码将在时间限制内执行。

int ind = *st.upper_bound(mp[i]);

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
# define ld long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
int n;
cin>>n;
set<int, greater<int>>st;
st.insert(-1);
map<int,int> mp;
int p[2*n];
char s[2*n];
for(int i=0;i<2*n;i++)
{
cin>>s[i];
if(s[i]=='+')
st.insert(i);
else
{
cin>>p[i];
mp[p[i]]=i;
}

}
for(int i=1;i<=n;i++)
{

int ind = *st.upper_bound(mp[i]);
if(ind==-1||st.find(ind)==st.end())
{
// if (-) come before +
cout<<"NO\n";
return;
}
st.erase(ind);
p[ind] = i;

}

// cout<<endl;
stack<int>stc;
for(int i=0;i<2*n;i++)
{
if(s[i]=='+')
stc.push(p[i]);
else
{
if(stc.top()==p[i])
stc.pop();
else
{
//if element not in order given in language
cout<<"NO\n";
return ;
}
}
}
cout<<"YES\n";
for(int i=0;i<2*n;i++)
{
if(s[i]=='+')
cout<<p[i]<<endl;
}
return;
}


int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
IOS
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}

最佳答案

set::upper_bound 将使用集合的功能来高效地搜索值(关于容器大小的对数)。
对于 std::upper_bound ,使用非LegacyRandomAccessIterators,例如std::set的迭代器(即LegacyBidirectionalIterator),迭代器增量的数量是线性的。

关于c++ - set.upper_bound()和upper_bound(set.begin(),set.end())STL之间的区别,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64536493/

31 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com