Main » 2013 September 28 » [NOIP2010模拟赛]区间
11:59 AM [NOIP2010模拟赛]区间 |
利用区间序,先排序O(nlgn)再O(n)求解#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #define N 100100 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; struct node { int L,R; }; node a[N],ans[N]; int cmp(node a,node b) { if (a.L<b.L) return 1; if (b.L<a.L) return 0; if (b.R<a.R) return 1; if (a.R<b.R) return 0; return 0; } int main() { int n,i; scanf("%d",&n); FOR(i,1,n) scanf("%d %d",&a[i].L,&a[i].R); sort(a+1,a+1+n,cmp); int p=0; ans[0].L=0;ans[0].R=0; FOR(i,1,n) { if (a[i].L>ans[p].R) { p++; ans[p].L=a[i].L; ans[p].R=a[i].R; }else { ans[p].R=max(ans[p].R,a[i].R); } } FOR(i,1,p) printf("%d %d\n",ans[i].L,ans[i].R); } |
|
|
| Total comments: 0 | |