2 条题解
-
1
#include <bits/stdc++.h> using namespace std; struct point { long long l, r; } a[200100]; bool cmp(point x, point y) { if (x.l == y.l) { return x.r < y.r; } else { return x.l < y.l; } } int main() { int t; scanf("%d", &t); for (int i = 1; i <= t; i++) { int n; scanf("%d", &n); long long min1 = 1e18, max1 = -1e16; for (int i = 1; i <= n; i++) // 求左边的最大值max1,求右边的最小值min1,当max1大于min1 // 说明一定存在相离的情况,不符合题意 { scanf("%lld%lld", &a[i].l, &a[i].r); max1 = max(a[i].l, max1); min1 = min(a[i].r, min1); } if (max1 > min1) { printf("No\n"); continue; } sort(a + 1, a + 1 + n, cmp); // 相离的情况判断完了,接着判断包含的情况,左边按从小到大排序 // max2的值表示排序后右边的值 long long max2 = a[1].r, z = 0; for (int i = 2; i <= n; i++) { // printf("%lld %lld\n",a[i].r,max2); if (a[i].r < max2) // 由于左边已经按从小到大排序,所以只要满足a[i].r<max2,就构成包含关系,不符合题意 { z = 1; break; } else { max2 = a[i].r; } } // 到此我们已将排除所有不符合的情况 if (z == 0) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }
信息
- ID
- 1205
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 177
- 已通过
- 18
- 上传者