首页 > 代码库 > uva---10020+贪心
uva---10020+贪心
区间覆盖问题,刘汝佳小白书P154页有具体思路;
代码例如以下:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef struct { int x,y; }P; P p[110000]; int cmp(P p1,P p2) { if(p1.x==p2.x) return p1.y<p2.y; return p1.x<p2.x; } int main() { int i,j,k,t,m,ans[110000],cnt; scanf("%d",&t); while(t--) { scanf("%d",&m); k=0; while(1) { int x,y; scanf("%d%d",&x,&y); if(!x&&!y) break; p[k].x=x; p[k].y=y; k++; } sort(p,p+k,cmp); cnt=0; int left=0,right,flag=0; for(i=0;i<k;) { right=0; while(p[i].x<=left&&i<k) { if(p[i].y>right) { right=p[i].y; j=i; } i++; } if(right==0) break; left=right; ans[cnt++]=j; if(right>=m) { flag=1; break; } } if(!flag) { printf("0\n"); if(t) printf("\n"); continue; } printf("%d\n",cnt); for(i=0;i<cnt;i++) printf("%d %d\n",p[ans[i]].x,p[ans[i]].y); if(t) printf("\n"); } return 0; }
uva---10020+贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。