[ CodeVS冲杯之路 ] P1214

　　不充钱，你怎么AC？

　　这道题类似于最长区间覆盖，仅仅是将最长区间改成了最多线段，我们贪心即可

　　先将线段直接右边-1，然后按左边为第一关键字，右边为第二关键字升序排序，我们发现对于以下这种情况，是可以直接将黑色的线段删除的，因为要求线段最多，也就是每个区间要最小。

　　最后从左往右扫，卡一个最右端点，遇到大于右端点的就更新，时间复杂度 O(n²)，删线段可以优化到 nlog₂n 但是 n 只有100就懒得打了~

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #define N 101

 using namespace std;

 struct line

 {

     int l,r;

 }

     a[N];

 bool f[N];

 int n,ans;

 bool cmp(line x,line y)

 {

     return (x.l<y.l)||((x.l==y.l)&&(x.r<y.r));

 }

 int main()

 {

     int i,j;

     scanf("%d",&n);

     for (i=;i<=n;i++)

     {

         scanf("%d%d",&a[i].l,&a[i].r);

         if (a[i].l>a[i].r) swap(a[i].l,a[i].r);

         a[i].r--;

         f[i]=;

     }

     sort(a+,a++n,cmp);

     for (i=;i<n;i++)

     {

         for (j=i+;j<=n;j++)

         {

             if (a[j].l>a[i].r) break;

             if (a[j].r<=a[i].r)

             {

                 f[i]=;

                 break;

             }

         }

     }

     j=-;

     for (i=;i<=n;i++)

     {

         if (f[i]||a[i].l<=j) continue;

         ans++;

         j=a[i].r;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

[ CodeVS冲杯之路 ] P1214

最新文章

热门文章