题目大意：求最终有多少张海报可见。
题目思路：最近想写一下矩形切割，当然，对于这道题不是很适合，不过可以过。
[cpp] #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define inf 0x3f3f3f3f #define uint unsigned __int64 #define M 1000000 struct node { int p1,p2,co; }a[M],now; int used[10100],total; int judge(node a,node b) { if(a.p2b.p2) return 0; else return 1; } void cut(node tmp) { int k1,k2; k1=max(tmp.p1,now.p1); k2=min(tmp.p2,now.p2); if(tmp.p1 { a[++total]=tmp; a[total].p2=k1-1; } if(tmp.p2>k2) { a[++total]=tmp; a[total].p1=k2+1; } } int main() { int t,i,j,l,r,n; scanf("%d",&t); while(t--) { scanf("%d",&n); total=0; for(i=1;i<=n;i++) { scanf("%d%d",&l,&r); now.p1=l;now.p2=r;now.co=i; for(j=total;j>=1;j--) { if(judge(now,a[j])) { cut(a[j]); a[j]=a[total--]; } } a[++total]=now; } memset(used,0,sizeof(used)); int num=0; for(i=1;i<=total;i++) { if(!used[a[i].co]) { used[a[i].co]=1; num++; } } printf("%d\n",num); } }