解题思路:
1.首先将每个区间按照右边界从小到大进行排序
2.然后把每个点从大到小进行排序,这样便可以使用lower_bound函数找倒第一个小于等于某个值的点
3.使用x记录上一个点的值,初始化为-1,这样方便处理
4.当一个区间的左边界大于x时候,需要从所有剩下的点中找到第一个小于等于右边界的点。如果没有找到,错误,如果找到的点不满足要求,也是错误。
注意事项: lower_bound使用
参考代码:
#include<iostream> #include<algorithm> #include<vector> using namespace std; const int N=10010,M=10010; typedef struct { int L,R; }region; region re[M]; vector<int>point; bool cmp(region a,region b) { return a.R<b.R; } int main(void) { int n,m,x,cnt=0,yes=true; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>x; point.push_back(x); } for(int i=1;i<=m;i++) cin>>re[i].L>>re[i].R; sort(re+1,re+m+1,cmp); sort(point.begin(),point.end(),greater<int>()); x=-1; for(int i=1;i<=m;i++) { if(x<re[i].L) { vector<int>::iterator it=lower_bound(point.begin(),point.end(),re[i].R,greater<int>()); if(it==point.end()) { yes=false; break; } x=*it; point.erase(it); cnt++; if(x<re[i].L) { yes=false; break; } } } if(yes) cout<<cnt; else cout<<-1; return 0; }
0.0分
2 人评分
【亲和数】 (C语言代码)浏览:495 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:543 |
WU-C语言程序设计教程(第三版)课后习题11.11 (C++代码)(想学链表的可以看看)浏览:1358 |
【计算直线的交点数】 (C语言代码)浏览:1453 |
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)浏览:529 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:668 |
简单的a+b (C语言代码)浏览:512 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:721 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:568 |
数列有序 (C语言代码)浏览:935 |