2 条题解
-
4
struct hui { int l, r; }; bool cmp(hui x, hui y) { if (x.l == y.l) { return x.r < y.r; } return x.l < y.l; } void sll() { int n; cin >> n; hui arr[n + 9] = {0}; int mi = inf; int ma = -inf; for (int i = 1; i <= n; i++) { cin >> arr[i].l >> arr[i].r; ma = max(ma, arr[i].l); mi = min(mi, arr[i].r); } if (ma > mi) { cout << "No" << '\n'; // 判断是不是相离,自己可以写几个情况看看 return; } sort(arr + 1, arr + n + 1, cmp); for (int i = 2; i <= n; i++) { if (arr[i].l != arr[i - 1].l && arr[i].r < arr[i - 1].r) { cout << "No" << '\n'; return; } // 因为我们的排序可以简单判断包含因为是先排序l, 那后面的l肯定大于等于前面的l, 首先我们可以肯定同l的情况下r是越来越大的, 所以我们只要判断l与前面不相等的情况下是不是后面的r >= 前面的r, 然后如果可以那r一直变大,就不用考虑前面的r了, 如果小于,那就出答案了,那也不用考虑前面的r了, 所以只要考虑l不同情况下的前后相邻r的大小关系; } cout << "Yes" << '\n'; } signed main() { ios::sync_with_stdio(0); cout.tie(0), cin.tie(0); int cs = 1; cin >> cs; while (cs--) { sll(); } return 0; } -
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; }
- 1
信息
- ID
- 1205
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 153
- 已通过
- 14
- 上传者