2 条题解

  • 0
    @ 2025-10-8 16:58:02
    #include<bits/stdc++.h>
    using namespace std;
    const int N=5e4+10;
    struct node{int x,y;}E[N];
    int b[2*N],a[2*N],d[2*N];
    int main()
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&E[i].x,&E[i].y);
            b[2*i-1]=E[i].x;
            b[2*i  ]=E[i].y;
        }
        sort(b+1,b+1+2*n);
        int m=unique(b+1,b+1+2*n)-b-1;
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;i++)
        {
            E[i].x=lower_bound(b+1,b+1+m,E[i].x)-b;
            E[i].y=lower_bound(b+1,b+1+m,E[i].y)-b;
            d[E[i].x]++;
            d[E[i].y+1]--;
        }
        int ans=0;
        memset(a,0,sizeof(a));
        for(int i=1;i<=m+1;i++)
        {
            a[i]=a[i-1]+d[i];
            ans=max(ans,a[i]);
        }
        printf("%d\n",ans);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:57:58
      #include<bits/stdc++.h>
      using namespace std;
      const int N=5e4+10;
      struct node{int x,y;}E[N];
      int b[2*N],a[2*N],d[2*N];
      int main()
      {
          int n;scanf("%d",&n);
          for(int i=1;i<=n;i++)
          {
              scanf("%d%d",&E[i].x,&E[i].y);
              b[2*i-1]=E[i].x;
              b[2*i  ]=E[i].y;
          }
          sort(b+1,b+1+2*n);
          int m=unique(b+1,b+1+2*n)-b-1;
          memset(d,0,sizeof(d));
          for(int i=1;i<=n;i++)
          {
              E[i].x=lower_bound(b+1,b+1+m,E[i].x)-b;
              E[i].y=lower_bound(b+1,b+1+m,E[i].y)-b;
              d[E[i].x]++;
              d[E[i].y+1]--;
          }
          int ans=0;
          memset(a,0,sizeof(a));
          for(int i=1;i<=m+1;i++)
          {
              a[i]=a[i-1]+d[i];
              ans=max(ans,a[i]);
          }
          printf("%d\n",ans);
          return 0;
      }
      • 1

      【一维差分】数轴最多覆盖数[USACO10OCT] Soda Machine G

      信息

      ID
      1587
      时间
      1000ms
      内存
      128MiB
      难度
      7
      标签
      递交数
      172
      已通过
      42
      上传者