题解

1 条题解

  • 0
    @ 2017-03-09 20:51:10
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    struct data{
        int x;
        int y;
        int z;
        bool operator <(const data &oth) const
        {
            if(x<oth.x) return 1;
            if(x>oth.x) return 0;
            return y<oth.y;
        }
    }cow[100003];
    int ef(int a,int b,int t)
    {    if(a==b) {
          if(cow[a].x>t)
          return a;  
          return 0;
          }               
         int mid=a+(b-a)/2;
         if(cow[mid].x<=t) return ef(mid+1,b,t);
         else return ef(a,mid,t);
    }
    int f[100004];
    int main()
    
    {  
        int b;
       scanf("%d",&b);
       for(int i=1;i<=b;i++)
       {
        scanf("%d%d",&cow[i].x,&cow[i].y);
        cow[i].z=cow[i].y-cow[i].x+1;
       }
       sort(cow+1,cow+1+b);
       f[b]=cow[b].z;
       for(int i=b-1;i>=1;i--)
        f[i]=max(f[i+1],f[ef(i+1,b,cow[i].y)]+cow[i].z);
       printf("%d",f[1]);
        return 0;
    }
    
  • 1

信息

难度
10
分类
(无)
标签
(无)
递交数
5
已通过
0
通过率
0%
上传者