竞选海报问题,用C语言实现!急
描述
数码城正在举行市长选举，城中各处贴满了竞选者的海报，这引起了一些市民的不满。因此城市委员会决定建造一座竞选墙，让参加竞选的人把自己的海报统 一贴到竞选墙上。张贴海报的规则是：
每一个候选人只能张贴一张海报；
海报的高度和墙的高度一样，而海报的宽度则是任意个 byte 宽（在数码城，byte 是个长度单位）；
竞选墙被分成很多段，每段的宽度是一个 byte；
竞选者的海报必须完整地覆盖一串连续的段。
委员会建立的竞选墙长度为 10,000,000 byte。竞选开始后，候选人可以把他们自己的海报张贴出来。然而，一些候选人却把自己的海报贴在了已经张贴了海报的墙面上，从而盖住了别人的海报。数码 城的人们都很好奇，最后有几个人的海报是可见（部分或全部）的呢？
你的任务就是在海报宽度、位置和张贴顺序这些数据的基础上，找出最终能有几个竞选者的海报能被人们看到。
输入
输入的第一行是一个整数，它表示数据的组数，之后是各组数据。
每组数据的第一行是一个整数 1 <= n <= 10000。后续的 n 行顺序地记录了 n 张海报张贴的位置，每一行有两个整数 li 和 ri，分别是第 i 张海报所占据的最左和最右段号。已知对于每一个 1 <= i <= n，1 <= li <= ri <= 10,000,000。当第 i 份海报张贴后，它会覆盖从 li, li+1,...ri 的所有段。
输出
针对每一组数据，输出最终可以显示出的海报的份数。
PS:本人一点思路没有,这个问题要怎样实现呢,数据结构我们只学了数组广义表 线性表 栈队列,不知道怎样解决,高手给个实现代码,或者提供下思路也行.
[解决办法]
似乎比较慢,差不多是N * N的复杂度.
没有记录显示海报的编号.
// 竞选海报墙纸.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <vector>#include <map>#include <list>using namespace std;typedef unsigned int size_type;void add(map<size_type,size_type> & v,pair<size_type,size_type> pSource){ if(pSource.second <= pSource.first) return ; pair<size_type,size_type> p1(0,0),p2(0,0); size_type iNum = 0; for(map<size_type,size_type>::iterator p = v.begin();p != v.end();){ if(p->second <= pSource.first){ ++ p; continue; } if(pSource.second <= p->first) break; if(iNum ++) p2 = *p; else p1 = *p; v.erase(p ++); } v.insert(pSource); if(iNum){//有重复部分 if(iNum == 1){//只有一个重叠 if(p1.first < pSource.first)//原有的前部分没有被覆盖 v.insert(pair<size_type,size_type>(p1.first,pSource.first)); if(pSource.second < p1.second)//原有的后半部分没有被覆盖 v.insert(pair<size_type,size_type>(pSource.second,p1.second)); } else{//有两个部分以上被覆盖 if(p1.first < pSource.first)//原有的前部分没有被覆盖 v.insert(pair<size_type,size_type>(p1.first,pSource.first)); if(pSource.second < p2.second)//原有的后半部分没有被覆盖 v.insert(pair<size_type,size_type>(pSource.second,p2.second)); } }}int _tmain(int argc, _TCHAR* argv[]){ map<size_type,size_type> m; size_type n ; cin >> n; for(size_type x = 0; x < n;++ x){ size_type a,b; cin>> a >> b; add(m,pair<size_type,size_type> (a,b)); } for(map<size_type,size_type>::iterator p = m.begin();p != m.end();++p){ cout<<p->first<<"---"<<p->second<<" "; } cout<<endl; return 0;}
[解决办法]
#include <iostream>using namespace std;#define LEN 20000#define NO_POSTER -2 //无海报#define MIX_POSTER -1 //混合(间断)海报#define NO_FLAG 0//线段树的静态表示,左边界,右边界,标志域,结点对应海报编号,海报能否看见的标记数组,结点数量,最终能看见的海报数量int left_bound[LEN],right_bound[LEN],flag[LEN],poster[LEN],ref[LEN],node_num,count_poster;//clear(int index),更新poster[index],flag[index],flag[left_child[index]],flag[right_child[index]]void clear(int index){ poster[index]=flag[index]; flag[2*index]=flag[index]; flag[2*index+1]=flag[index]; flag[index]=NO_FLAG;}//创建线段树void construct(int left,int right,int num=1){ ++node_num; left_bound[num]=left; right_bound[num]=right; poster[num]=NO_POSTER; if(left+1<right) { int mid=(left+right)/2; construct(left,mid,2*num); construct(mid,right,2*num+1); }}//贴海报void insert(int index,int left,int right,int num){ if(flag[index]!=NO_FLAG) //如果有标志域,说明被完全覆盖过,所以更新自己的海报信息与孩子的标志域******PS:标志域的作用就是当前结点与之下子结点信息一致时,免去一次性全部更新的浪费 //先用标志域存储起来,下次需要用时临时更新需要的结点获得信息..看下一条注释! { clear(index); } if(left==left_bound[index]&&right_bound[index]==right)//例如: 如果某结点完全覆盖,那么它的子结点与该结点继承同一海报,所以这时候用标志域比用poster[]记录要有效得多！看下一条注释！ { flag[index]=num; return; } else//如果没有完全覆盖,那么就不能标志当前结点的flag,因为子结点与该结点没有相同的特征,子结点只是零散的覆盖该结点，所以这时只要修改poster[index]为混合标记就可以了. { poster[index]=MIX_POSTER; int mid=(left_bound[index]+right_bound[index])/2; if(left<mid&&right<=mid) { insert(2*index,left,right,num); } if(left<mid&&right>mid) { insert(2*index,left,mid,num); insert(2*index+1,mid,right,num); } if(left>=mid&&right>mid) { insert(2*index+1,left,right,num); } }}//数海报数量,这里完全依赖于poster[]的记录来数海报数量,所以必须根据flag刷新被完全覆盖结点的海报编号. 判断条件依赖于: poster[] 中有编号，混合海报，没有覆盖海报，一共三个情况。void count(int index){ if(flag[index]!=NO_FLAG) { clear(index); } if(poster[index]!=NO_POSTER) { if(poster[index]!=MIX_POSTER) { if(ref[poster[index]]==0) { ref[poster[index]]=1; ++count_poster; } } else { count(2*index); count(2*index+1); } }}int main(){ node_num=0; count_poster=0; memset(ref,0,sizeof(ref)); int num;//海报数量 int left,right;//海报覆盖范围 cin>>left>>right>>num;//输入墙的范围 construct(left,right);//构造线段树 for(int cnt=1;cnt<=num;++cnt) { cin>>left>>right; insert(1,left,right,cnt); } count(1); cout<<count_poster<<endl; }