2 条题解
-
1
用优先队列,优先右边值最小的
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1; while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-') fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48, rx=getchar();return ra*fh;} struct node { int l; int r; bool operator < (const node &x) const { return r>x.r; } }; bool cmp(node x,node y) { return x.l<y.l; } node nt; node cur; int n; vector<node> a; int main() { n=read(); for(int i=0;i<n;i++) { nt.l=read(); nt.r=read(); a.push_back(nt); } sort(a.begin(),a.end(),cmp); priority_queue<node> q; q.push(a[0]); for(int i=1;i<n;i++) { cur = q.top(); if(cur.r<a[i].l) { q.pop(); } q.push(a[i]); } printf("%d\n",q.size()); return 0; }
-
1
用线段树暴力区间加1
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1; while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-') fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48, rx=getchar();return ra*fh;} const int N = 1000005; struct { int l,r,val,tag; }t[3000005]; void pushdown(int k) { if(t[k].l==t[k].r) return; int tag = t[k].tag; t[k].tag=0; if(tag) { t[k<<1].tag =t[k<<1].tag+tag; t[k<<1|1].tag=t[k<<1|1].tag+tag; t[k<<1].val=t[k<<1].val+tag; t[k<<1|1].val=t[k<<1|1].val+tag; } } void build(int k,int l,int r) { t[k].l = l; t[k].r = r; if(l==r) return ; int mid = (l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); } void update(int k,int x,int y,int val) { pushdown(k); int l = t[k].l; int r = t[k].r; if(l==x&&r==y) { t[k].tag ++; t[k].val ++; return ; } int mid = (l+r)>>1; if(y<=mid) update(k<<1,x,y,val); else if(x>mid) update(k<<1|1,x,y,val); else { update(k<<1,x,mid,val); update(k<<1|1,mid+1,y,val); } t[k].val=max(t[k<<1].val,t[k<<1|1].val); } int query(int k,int x) { pushdown(k); int l = t[k].l; int r = t[k].r; if(l==r) { return t[k].val; } int mid = (l+r)>>1; if(x<=mid) { return query(k<<1,x); } else { return query(k<<1|1,x); } } int n; int l,r; int main() { ios_base::sync_with_stdio(false); cin >> n; build(1,1,1000000); for(int i=0;i<n;i++) { cin >> l>>r; update(1,l,r,1); } pushdown(1); cout << t[1].val<<endl; return 0; }
- 1
信息
- ID
- 1651
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 15
- 已通过
- 5
- 上传者