箱子_线段树

2019-11-08 01:04:27

字体：大中小

来源：转载

供稿：网友

题目描述

桌子上零散地放着若干个盒子，桌子的后方是一堵墙。如右图所示。现在从桌子的前射来一束平行光，把盒子的影子投射到了墙上。问影子的总宽度是多少？

思路

用线段树记录下每一个区间，暴力求解就可以了 O(logn)

#include <stdio.h>struct tree{ int l,r,c;}t[1000];int insert(int f,int x,int y){ if (t[f].c==0) { int m=(t[f].l+t[f].r)/2; if (t[f].l==x&&t[f].r==y) t[f].c=1; else if (y<=m) insert(f*2,x,y); else if (x>=m) insert(f*2+1,x,y); else { insert(f*2,x,m); insert(f*2+1,m,y); } }}int count(int f){ if (t[f].c==1) return t[f].r-t[f].l; else if (t[f].r-t[f].l==0) return 0; else return count(f*2)+count(f*2+1);}int create(int f){ if (t[f].l!=t[f].r-1) { int m=(t[f].l+t[f].r)/2; t[f*2].l=t[f].l; t[f*2].r=m; t[f*2+1].l=m; t[f*2+1].r=t[f].r; create(f*2); create(f*2+1); }}int main(){ int n,m; scanf("%d%d",&n,&m); t[1].l=1; t[1].r=n; create(1); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); insert(1,x,y); } PRintf("%d/n",count(1));}

上一篇：算法提高身份证号码升级

下一篇：LeetCode 88 --- Merge Sorted Array