显示代码纯文本
/*
暴力：按题目要求做，最坏O(n^2)
正解：按照草堆从大到小排序，2个set维护草堆旁边的两个草堆，如果
不能冲出区间则对这个区间染色，最后区间求并然后统计长度即可，
O(n^log2(n))
证明：见评论
*/
#include <fstream>
#include <algorithm>
#include <map>
#include <set>
#define N 100010
using namespace std;
ifstream in("trapped.in");
ofstream out("trapped.out");
int n,m=0,top=0;
class point//既表示区间，又表示Sj,Pj
{
public:
int x,y;
void make(int a,int b)
{
x=a;
y=b;
}
void print()
{
out<<x<<' '<<y<<endl;
}
}P[N],seg[3*N];
bool operator <(point a,point b)//按Sj排序
{
if(a.x==b.x)return a.y<b.y;
return a.x>b.x;
}
bool com(point a,point b)//区间按左端点排序
{
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
map<int,int> F;
void lisanhua()
{
int i;
for(i=1;i<=n;i++)F[P[i].y]=i;
}
void read()
{
int i;
in>>n;
for(i=1;i<=n;i++)in>>P[i].x>>P[i].y;
sort(P+1,P+n+1);
}
void arraymerge()//区间合并
{
int i;
for(i=1;i<m;i++)
{
if(seg[i].y>=seg[i+1].y)
{
seg[i+1]=seg[i];
seg[i].make(-1,-1);
}
else if(seg[i].y>=seg[i+1].x)
{
seg[i+1].x=seg[i].x;
seg[i].make(-1,-1);
}
}
int ans=0;
for(i=1;i<=m;i++)if(seg[i].x!=-1)ans+=seg[i].y-seg[i].x;
//加上区间长度
out<<ans<<endl;
}
void work()
{
int i,len;
int left,right;
set<int> S;
set<int,greater<int> >T;
set<int>::iterator it;
set<int,greater<int> >::iterator ot;
for(i=1;i<=n;i++)
{
//右边
it=S.upper_bound(P[i].y);
if(it!=S.end())
{
left=F[P[i].y];right=F[*it];
len=P[right].y-P[left].y;//最大速度
if(len<=P[left].x&&len<=P[right].x)seg[++m].make(P[left].y,P[right].y);
}
//左边
ot=T.upper_bound(P[i].y);
if(ot!=T.end())
{
left=F[*ot];right=F[P[i].y];
len=P[right].y-P[left].y;//最大速度
if(len<=P[left].x&&len<=P[right].x)seg[++m].make(P[left].y,P[right].y);
//如果最大速度>左边草堆的数量或者右边草堆的数量，就不会被围困
//否则添加一个区间
}
S.insert(P[i].y);
T.insert(P[i].y);
}
for(i=1;i<=n;i++)seg[++m].make(P[i].y,P[i].y);
sort(seg+1,seg+m+1,com);
arraymerge();
}
int main()
{
read();
lisanhua();
work();
return 0;
}
Satoshi