求助

P1105 平台

本题的数据很糟糕。题目中说明平台不会重叠,但是实际上测试数据中平台会发生重叠,您需要按照特定的顺序将平台排序,否则就无法AC。 排序先按照高度升序排列,如果两个平台的高度相同,按照序号较大的排列在先的原则进行排序,最后在比较时,只要找到了相应的平台就退出,违反上述任何一点,都可能造成输出与标准输出不同,从而导致WA。 题目数据的问题,本来是一道简单的题目,被搞得复杂了。 建议管理员修一下。 以下是在您的代码基础上修改而得的AC代码。 ``` #include<bits/stdc++.h> #define s(x) scanf("%d",&x); #define p(x) printf("%d",x); #define c cout<<endl; #define d cout<<" "; using namespace std; int MIN, bo, n, p[1010][5]; struct node { int h, l, r, xh; bool operator<(const node & nd) const { if (h == nd.h) return xh > nd.xh; return h < nd.h; } }a[1010]; void qsort(int l, int r) { int i = l, j = r, mid = a[(l + r) / 2].h; while (i <= j) { while (a[i].h < mid) i++; while (mid < a[j].h) j--; if (i <= j) { swap(a[i], a[j]); i++; j--; } } if (l < j) qsort(l, j); if (i < r) qsort(i, r); } int main() { cin >> n; for (int i = 1; i <= n; i++) { s(a[i].h) s(a[i].l) s(a[i].r) a[i].xh = i; } //qsort(1,n); sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) { MIN = n + 1; bo = 0; // ! p[a[i].xh][1] = 0; for (int j = i - 1; j >= 1; j--) { if (a[j].l < a[i].l && a[j].r > a[i].l) { bo = 1; MIN = min(MIN, a[j].xh); break; } } if (bo == 1) p[a[i].xh][1] = MIN; MIN = n + 1; bo = 0; // ! p[a[i].xh][2] = 0; for (int j = i - 1; j >= 1; j--) { if (a[j].l < a[i].r && a[j].r > a[i].r) { bo = 1; MIN = min(MIN, a[j].xh); break; } } if (bo == 1) p[a[i].xh][2] = MIN; } for (int i = 1; i <= n; i++) { cout << p[i][1] << " " << p[i][2] << endl; } return 0; } ``` @[zhjzhmh](/user/233815)
by metaphysis @ 2020-06-07 19:20:42


|