Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 说谎。。。。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: