1661.cpp

非常好的C++学习源码,里面包括各种算法的实现,二叉的的前中后序遍历等

#include<iostream>
using namespace std;

struct b
{
	int x1;
	int x2;
	int h1;
};

b c[1001];
int nleft[1001],nright[1001];

int compare(const void *e1,const void *e2)
{
	b *p1,*p2;
	p1=(b *)e1;
	p2=(b *)e2;
	return (p2->h1)-(p1->h1);
}

int main()
{
	int t,i,j,n,x,y,h,k,p1,q1,p2,q2;
	cin>>t;
	for (i=1;i<=t;i++)
	{
		cin>>n>>x>>y>>h;
		c[0].x1=x;
		c[0].x2=x;
		c[0].h1=y;
		for (j=1;j<=n;j++)
			cin>>c[j].x1>>c[j].x2>>c[j].h1;
		qsort(c,n+1,sizeof(b),compare);
		nleft[n]=c[n].h1;
		nright[n]=c[n].h1;
		for (j=n-1;j>=0;j--)
		{
			p1=0;
			for (k=j+1;k<=n;k++)
				if ((c[k].x1<=c[j].x1)&&(c[k].x2>=c[j].x1))
				{
					q1=k;
					p1=1;
					break;
				}
			if (p1==0)
			{
				if (c[j].h1<=h)
					nleft[j]=c[j].h1;
				else
					nleft[j]=-1;
			}
			if ((p1==1)&&(c[j].h1-c[q1].h1<=h))
			{
				if ((nleft[q1]!=-1)&&(nright[q1]!=-1))
				{
					if (c[j].x1-c[q1].x1+nleft[q1]>c[q1].x2-c[j].x1+nright[q1])
						nleft[j]=c[j].h1-c[q1].h1+c[q1].x2-c[j].x1+nright[q1];
					else
						nleft[j]=c[j].h1-c[q1].h1+c[j].x1-c[q1].x1+nleft[q1];
				}
				else 
				{
					if ((nleft[q1]==-1)&&(nright[q1]==-1))
						nleft[j]=-1;
					else
					{
						if (nleft[q1]==-1)
							nleft[j]=c[j].h1-c[q1].h1+c[q1].x2-c[j].x1+nright[q1];
						if (nright[q1]==-1)
							nleft[j]=c[j].h1-c[q1].h1+c[j].x1-c[q1].x1+nleft[q1];
					}
				}
			}
			if ((p1==1)&&(c[j].h1-c[q1].h1>h))
				nleft[j]=-1;
			p2=0;
			for (k=j+1;k<=n;k++)
				if ((c[k].x1<=c[j].x2)&&(c[k].x2>=c[j].x2))
				{
					q2=k;
					p2=1;
					break;
				}
			if (p2==0)
			{
				if (c[j].h1<=h)
					nright[j]=c[j].h1;
				else
					nright[j]=-1;
			}
			if ((p2==1)&&(c[j].h1-c[q2].h1<=h))
			{
				if ((nright[q2]!=-1)&&(nleft[q2]!=-1))
				{
					if (c[j].x2-c[q2].x1+nleft[q2]>c[q2].x2-c[j].x2+nright[q2])
						nright[j]=c[j].h1-c[q2].h1+c[q2].x2-c[j].x2+nright[q2];
					else
						nright[j]=c[j].h1-c[q2].h1+c[j].x2-c[q2].x1+nleft[q2];
				}
				else
				{
					if ((nleft[q2]==-1)&&(nright[q2]==-1))
						nright[j]=-1;
					else
					{
						if (nleft[q2]==-1)
							nright[j]=c[j].h1-c[q2].h1+c[q2].x2-c[j].x2+nright[q2];
						if (nright[q2]==-1)
							nright[j]=c[j].h1-c[q2].h1+c[j].x2-c[q2].x1+nleft[q2];
					}
				}
			}
			if ((p2==1)&&(c[j].h1-c[q2].h1>h))
				nright[j]=-1;
		}
		cout<<nleft[0]<<endl;
	}
	return 0;
}