主题链接:点击打开链接
升序右键点。采取正确的点
删边暴力
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <iostream> #include <map> #include <set> #include <math.h> using namespace std; #define inf 10000000 #define ll int #define N 2105 #define L(x) (x<<1) #define R(x) (x<<1|1) inline ll Mid(ll a,ll b){return (a+b)>>1;} ll n; struct node{ ll x,y; }a[N]; bool cmp(node a,node b){ if(a.y==b.y)return a.x<b.x; return a.y<b.y; } vector<ll>ans; ll h[N]; int main(){ ll i, j; while(~scanf("%d",&n)){ for(i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; if(a[i].x>a[i].y)swap(a[i].x,a[i].y); } memset(h, 0, sizeof h); sort(a+1,a+n+1,cmp); ans.clear(); for(i = 1; i <=n;i++)if(!h[i]){ ans.push_back(a[i].y); for(j=i;j<=n;j++) { if(a[j].x<=a[i].y && a[i].y<=a[j].y) h[j] = 1; } } cout<<ans.size()<<endl; for(i=0;i<ans.size();i++) printf("%d%c",ans[i],i==((ll)ans.size()-1)?'\n':' '); } return 0; } /* 3 40 -83 52 -80 -21 -4 */ /* struct node{ ll l, r, id; ll maxx,val,lmaxx; }tree[N]; void push_down(ll id){ if(tree[id].l==tree[id].r)return ; if(tree[id].val){ tree[L(id)].val += tree[id].val; tree[R(id)].val += tree[id].val; tree[L(id)].lmaxx += tree[id].val; tree[L(id)].maxx += tree[id].val; tree[R(id)].lmaxx += tree[id].val; tree[R(id)].maxx += tree[id].val; tree[id].val = 0; } } void build(ll l, ll r, ll id){ tree[id].l = l, tree[id].r = r; tree[id].maxx = tree[id].val = 0; tree[id].lmaxx = 0; if(l==r)return ; ll mid = Mid(l,r); build(l,mid,L(id)); build(mid+1,r,R(id)); } void updata(ll l, ll r, ll val, ll id){ push_down(id); if(l == tree[id].l && tree[id].r == r){ tree[id].val += val; tree[id].maxx += val; tree[id].lmaxx += val; return; } ll mid = Mid(tree[id].l, tree[id].r); if(mid<l)updata(l,r,val,R(id)); else if(r<=mid) updata(l,r,val,L(id)); else { updata(l,mid,val,L(id)); updata(mid+1,r,val,R(id)); } tree[id].maxx = max(tree[L(id)].maxx, tree[R(id)].maxx); tree[id].lmaxx = tree[L(id)].lmaxx; } struct hehe{ ll val, x; hehe(ll a=0,ll b=0):val(a),x(b){} bool operator<(const hehe&a)const{ if(a.val==val)return a.x<x; return a.val>val; } }; hehe query(ll l, ll r, ll id){ push_down(id); if(l == tree[id].l && tree[id].r == r && tree[id].lmaxx==tree[id].maxx) return hehe(tree[id].maxx, tree[id].l); ll mid = Mid(tree[id].l, tree[id].r); if(mid<l)return query(l,r,R(id)); else if(r<=mid)return query(l,r,L(id)); else return max(query(l,mid,L(id)),query(mid+1,r,R(id))); } set<ll>myset; set<ll>::iterator p; map<ll,ll>mp; ll pos[N]; vector<ll>ans; int use[N]; int main(){ ll i, j, u, v; while(cin>>n){ myset.clear(); mp.clear(); ans.clear(); for(i=1;i<=n;i++){ cin>>x[i]>>y[i]; if(x[i]>y[i])swap(x[i],y[i]); myset.insert(x[i]); myset.insert(y[i]); use[i] = true; } ll siz = 1; for(p=myset.begin(); p!=myset.end(); p++, siz++) { pos[siz] = *p; mp.insert(pair<ll,ll>(*p,siz)); } for(i=1;i<=n;i++) { x[i] = mp.find(x[i])->second; y[i] = mp.find(y[i])->second; } build(1,siz-1,1); for(i=1;i<=n;i++) updata(x[i],y[i],1,1); while(tree[1].maxx){ hehe now = query(1,siz-1,1); ans.push_back(pos[now.x]); for(i=1;i<=n;i++) if(x[i]<=now.x&&now.x<=y[i] && use[i]) updata(x[i],y[i],-1,1), use[i] = false; } cout<<ans.size()<<endl; for(i=0;i<ans.size();i++) printf("%d%c",ans[i],i==((ll)ans.size()-1)?'\n':' '); } return 0; } /**/
版权声明:本文博客原创文章,博客,未经同意,不得转载。
本文转自mfrbuaa博客园博客,原文链接http://www.cnblogs.com/mfrbuaa/p/4757158.html,如需转载请自行联系原作者