首页 > 代码库 > set 代替splay查找前驱后继

set 代替splay查找前驱后继

例题:HNOI2012 营业额统计

http://www.cnblogs.com/TheRoadToTheGold/p/6372009.html

#include<cstdio>#include<set>#include<algorithm>using namespace std;set<int>s;int n,x,tmp,l,r,mid,w,k;int ans;int main(){    scanf("%d",&n);    scanf("%d",&x);    s.insert(x);    ans+=x;     for(int i=1;i<n;i++)    {        scanf("%d",&x);        set<int>::iterator a=s.lower_bound(x);        set<int>::iterator b=a;        if(a!=s.begin()) a--;        if(b==s.end()) b--;        ans+=min(abs(x-*a),abs(*b-x));        s.insert(x);    }    printf("%d",ans);}

 

set 代替splay查找前驱后继