题目是图片形式给出的,只能贴出地址:
http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=302
思路:
对于区间[Li,Ri),按照Li排序,然后对于每个方块区间[Li,Ri),判断当前所有层中最右边的方块的Rk是否小于等于Li,如果存在,则将[Li,Ri)放入该层,如果不存在,则新加一层。更新此层最右边方块为Ri。
开始的时候用数组Floor记录,每次扫描没一层,结果超时。
超时代码:
#include<iostream> #include<algorithm> using namespace std; #define Max 100005 struct Range{ int left; int right; }; Range data[Max]; int Floor[Max]; int cmp(const Range &a,const Range &b) { return a.left<b.left; } int main() { int n; while(~scanf("%d",&n)) { int high=1; for(int i=0;i<n;i++) { scanf("%d%d",&data[i].left,&data[i].right); Floor[i]=0; } sort(data,data+n,cmp); for(int i=0;i<n;i++) { int flag=false; for(int k=1;k<=high;k++) { if(Floor[k]<=data[i].left) { flag=true; Floor[k]=data[i].right; break; } } if(flag==false) Floor[high++]=data[i].right; } printf("%d\n",high); } }
后来用优先队列,记录最小的Rk,AC
代码:
#include<iostream> #include<algorithm> #include<queue> #include<functional> using namespace std; #define Max 100005 struct Range{ int left; int right; }; Range data[Max]; int cmp(const Range &a,const Range &b) { return a.left<b.left; } int main() { int n; while(~scanf("%d",&n)) { int high=1; for(int i=0;i<n;i++) scanf("%d%d",&data[i].left,&data[i].right); sort(data,data+n,cmp); priority_queue<int,vector<int>,greater<int> >que; que.push(data[0].right); for(int i=1;i<n;i++) { if(que.top()<=data[i].left) que.pop(); else high++; que.push(data[i].right); } printf("%d\n",high); } }
相关推荐
BOJ的题目1023. Ancient Keyboard解法 源代码
boj 上08 09 年复试模拟题的答案
boj:算法
JAVA_BOJ
Algorithm-BOJ.zip,BekJon在线法官(Java,Kotlin,SWIFT)和PS路线图,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
BOJ
Algorithm-BOJ-PSJ.zip,Baykon在线判断JAVA问题解决方法(第二章),算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-BOJ-AutoCommit.zip,当您解决baekjoon online judge的问题时,它会自动提交并推送到远程存储库。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-boj-auto-submit.zip,日本央行cli提交脚本,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
资源分类:Python库 所属语言:Python 资源全名:boj-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的,全数字化且可重复使用的着色书,可用于 通过这本图画书展示您的创造力,其中包括Boj和朋友。 一本有趣的全数字可重复使用的图画书,专为孩子,父母...
解决问题 Boj.kr
欢迎来到PS_BOJ 이곳은... J이한BOJ문제들의AC코드들이입니다。 안내 :check_mark: C ++ Python으로풀이합니다。 :check_mark: ++ C ++풀이하며 long long 필요하거나으으으으으으으으으끔씩만끔씩만끔씩만끔씩만...
BOJ:日本央行