Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!

说谎。。。。DISCUSS里有的数据我都测试光了。。。WA的无话可说

Posted by 4053040 at 2010-03-08 20:26:20 on Problem 1661 and last updated at 2010-03-08 20:29:03
In Reply To:也奉献社会,这组数据过了肯定AC!! Posted by:xiaofengsheng at 2009-04-24 18:30:55
#include<iostream>
using namespace std;
#define MAX_N 1020
#define INFINITE 1000000

struct Platform
{
	int l, r, h;
}; Platform platform[MAX_N];

int cmp( const void *a ,const void *b)  
{  
	return (*(Platform *)b).h > (*(Platform *)a).h ? 1 : -1;         //老天啊。。。。。看了两天 排序排反了。。。
}  



int main()
{
	int i, j;
	int t, N, X, Y, MAX;
	bool used[MAX_N][2];
	int leftmin[MAX_N], rightmin[MAX_N];
	int temp, sign;

	cin >> t;
	while(t --) {
		cin >> N >> X >> Y >> MAX;
		platform[0].h = Y;
		for(i = 1; i <= N; i ++)   //从1开始
			cin >> platform[i].l >> platform[i].r >> platform[i].h;
		qsort(platform, N + 1, sizeof(platform[0]), cmp);

		memset(used, 0, sizeof(used));
		//memset(leftmin, 0, sizeof(leftmin));      //大失误。。。怎么能初始化0.。。应该为一个大值
		//memset(rightmin, 0, sizeof(rightmin));
		for(i = 1; i < N + 2; i ++)
			leftmin[i] = rightmin[i] = INFINITE;
		platform[0].l = platform[0].r = X;     //初始坐标为给定的X 
	
		platform[N + 1].h = 0;                 //地面高度为0
		platform[N + 1].l = -INFINITE;
		platform[N + 1].r = INFINITE;     //地面左右界为无穷
		leftmin[0] = rightmin[0] = 0;
		for(i = 0; i <= N; i ++) {
			for(j = i + 1; j <= N + 1; j ++) {
				if(!used[i][0]) {          // used[][0]为左 [][1]为右
					if(platform[i].l > platform[j].l && platform[i].l <= platform[j].r) {
						if(platform[i].h - platform[j].h > MAX)
							leftmin[i] = INFINITE;
						else {
							temp = leftmin[i] + platform[i].l - platform[j].l;
							if(temp < leftmin[j])
								leftmin[j] = temp;
							temp = leftmin[i] + platform[j].r - platform[i].l;
							if(temp < rightmin[j])
								rightmin[j] = temp;
						}		
						used[i][0] = 1;
					}
				}
				if(!used[i][1]) {
					if(platform[i].r < platform[j].r && platform[j].l <= platform[i].r) {
						if(platform[i].h - platform[j].h > MAX)
							rightmin[i] = INFINITE;
						else {
							temp = rightmin[i] + platform[i].r - platform[j].l;
							if(temp < leftmin[j])
								leftmin[j] = temp;
							temp = rightmin[i] + platform[j].r - platform[i].r;
							if(temp < rightmin[j])
								rightmin[j] = temp;
						}	
						used[i][1] = 1;
					}
				}
				if(used[i][0] && used[i][1])        // i + 1继续循环
					break;
			}
		}
		//for(i = 0; i <= N; i ++) {
		//	cout << "leftmin" << leftmin[i] << endl;
		//}
		int minl = leftmin[N];          //输出
		int minr = rightmin[N];
		for(i = 0; i < N; i ++) {
			sign = 0;
			for(j = i + 1; j <= N; j ++) {
				if(platform[i].l > platform[j].l && platform[i].l < platform[j].r) {
					sign = 1;
					break;
				}
			}
			//cout <<">>>"<< leftmin[i] << endl;
			if(sign == 0) {
				if(minl > leftmin[i])
					minl = leftmin[i];
			}
		}
		for(i = 0; i < N; i ++) {
			sign = 0;
			for(j = i + 1; j <= N; j ++) {
				if(platform[i].r > platform[j].l && platform[i].r < platform[j].r) {
					sign = 1;
					break;
				}
			}
			if(sign == 0) {
				if(minr > rightmin[i])
					minr = rightmin[i];
			}
		}
		if(minl > minr)
			cout << minr + Y << endl;
		else
			cout << minl + Y << endl;
	}
	return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator