2 条题解

  • 4
    @ 2025-11-16 23:31:53
    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
      @ 2025-11-15 19:30:30
      #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
      上传者