1661.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"

long a[1002][3];
long b[1002][2];
void px(int n,int m)
{int s,i=n+1,j=m;
if(n>=m)return;

while(i<j)
{
while(a[n][2]>=a[i][2]&&i<j)i++;
while(a[n][2]<=a[j][2]&&j>i)j--;

if(a[i][2]>a[j][2]){s=a[i][2];a[i][2]=a[j][2];a[j][2]=s;
s=a[i][1];a[i][1]=a[j][1];a[j][1]=s;
s=a[i][0];a[i][0]=a[j][0];a[j][0]=s;}
}

if(a[i][2]>a[n][2])i--;

s=a[i][2];a[i][2]=a[n][2];a[n][2]=s;
s=a[i][1];a[i][1]=a[n][1];a[n][1]=s;
s=a[i][0];a[i][0]=a[n][0];a[n][0]=s;

px(n,i-1);
px(i+1,m);
}


int main()
{long t,n,x0,y0,max,i,j,k1,k2;long t1,t2,s;
cin>>t;
for(;t>0;t--)
{cin>>n;
//for(i=0;i<n;i++)b[i][0]=b[i][1]=0;
cin>>x0>>y0>>max;
for(i=1;i<=n;i++)cin>>a[i][0]>>a[i][1]>>a[i][2];
a[0][0]=-21000;
a[0][1]=21000;
a[0][2]=0;
n++;
px(0,n-1);
b[0][0]=b[0][1]=0;
for(i=1;i<n;i++)
{j=i;k1=k2=1;b[i][0]=b[i][1]=9999999;
while(k1||k2)
{j--;if(a[i][2]-a[j][2]>max)break;
if(k1&&a[j][0]<=a[i][0]&&a[j][1]>=a[i][0]){t1=b[j][0]+a[i][0]-a[j][0];t2=b[j][1]+a[j][1]-a[i][0];
b[i][0]=t1<t2?t1:t2;
if(j==0)b[i][0]=0;
b[i][0]+=a[i][2]-a[j][2];
k1=0;}

if(k2&&a[j][0]<=a[i][1]&&a[j][1]>=a[i][1]){t1=b[j][0]+a[i][1]-a[j][0];t2=b[j][1]+a[j][1]-a[i][1];
b[i][1]=t1<t2?t1:t2;
if(j==0)b[i][1]=0;
b[i][1]+=a[i][2]-a[j][2];
k2=0;}
}
}
s=0;
for(i=n-1;i>=0;i--)
if(a[i][2]<=y0&&a[i][0]<=x0&&a[i][1]>=x0){if(i==0){s=y0;break;}
	t1=b[i][0]+x0-a[i][0];t2=b[i][1]+a[i][1]-x0;s=t1<t2?t1:t2;s+=y0-a[i][2];break;}

cout<<s<<endl;
}
return 1;
}