pku1661.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <algorithm>
#define size 1100
using namespace std;

typedef struct Board
{
	int l, r, h, lt, rt;
} Board;

Board b[size];
int N, X, H, MAX;
int ans;

bool cmp(const Board &a, const Board &b)
{
	return a.h > b.h;
}

bool Between(int l, int m, int r)
{
	return l <= m && m <= r;
}

void Do(int h, int x, int t, int id)
{
	int tmpt;
	while (id < N && h - b[id].h <= MAX && !Between(b[id].l, x, b[id].r)) id++;
	if (h - b[id].h <= MAX && id < N && Between(b[id].l, x, b[id].r))
	{
		tmpt = t + (x - b[id].l) + (h - b[id].h);
		if (b[id].lt == -1 || b[id].lt > tmpt)
		{
			b[id].lt = tmpt;
		}
		tmpt = t + (b[id].r - x) + (h - b[id].h);
		if (b[id].rt == -1 || b[id].rt > tmpt)
		{
			b[id].rt = tmpt;
		}
	}
	else if (id == N && h <= MAX)
	{
		tmpt = t + h;
		if (ans == -1 || ans > tmpt)
		{
			ans = tmpt;
		}
	}
}

void Solve()
{	
	int i;
	scanf("%d %d %d %d", &N, &X, &H, &MAX);
	memset(b, -1, sizeof(b));
	ans = -1;
	for (i = 0; i < N; i++)
	{
		scanf("%d %d %d", &b[i].l, &b[i].r, &b[i].h);
	}
	sort(b, b + N, cmp);
	Do(H, X, 0, 0);
	for (i = 0; i < N; i++)
	{
		if (b[i].lt != -1)
		{
			Do(b[i].h, b[i].l, b[i].lt, i + 1);
			Do(b[i].h, b[i].r, b[i].rt, i + 1);
		}
	}
	printf("%d\n", ans);
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		Solve();
	}
	return 0;
}