题目描述
维护一个集合,支持动态维护大小顺序,查询一个元素的前驱后继
c++ STL set
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std; set< pair<int,int> > s;
int n,m;
int main(){
cin>>n;
s.insert({INT_MIN,0});
s.insert({INT_MAX,0});
int a,b;cin>>a;
s.insert({a,1});
cin>>b;
cout<<abs(a-b)<<" 1"<<endl;
s.insert({b,2});
for(int i=3;i<=n;i++){
int x;cin>>x;
set<pair<int,int> >::iterator it;
it=s.upper_bound({x,0});
if(it==s.begin()){
cout<<abs(it->first-x)<<" "<<it->second<<endl;
s.insert({x,i});
continue;
}
if(it==s.end())
{
it--;
cout<<abs(it->first-x)<<" "<<it->second<<endl;
/*int sum=1;int q=*it;it=s.begin();
while(*it!=q){
it++;sum++;
}
cout<<sum<<endl;*/
s.insert({x,i});
continue;
}
int p1=abs(it->first-x);
it--;
int p2=abs(it->first-x);
if(p2<=p1){
cout<<p2<<" "<<it->second<<endl;
s.insert({x,i});
}
/*int sum=1;int q=*it;it=s.begin();
while(*it!=q){
it++;sum++;
}
cout<<sum<<endl;
}*/
else{
cout<<p1<<" ";
it++;
cout<<it->second<<endl;
/*int sum=1;it++;int q=*it;it=s.begin();
while(*it!=q){
it++;sum++;
}
cout<<sum<<endl;
}*/
s.insert({x,i});
}
}
}
因为upper_bound函数不会判断边界,所以要加特判
我们读者太难了!
我们读者太难了!
我们读者太难了!
您的Markdown有点看着有点难受