USACO[Elite 2010 February Competition/gold]corral

今天准备四月的USACO金组月赛（第一次有资格参加，当然要准备一下），所以找了这场金组的题目来做。

然后，废话到此为止。

首先，第一题和APIO2009的会议中心一题有些像（不过现在我还没做出它），要用到一点贪心。

我的程序中最开始写的是动态规划，但是会TLE13（没想到数据会这么变态），后来改了一下，就AC了。但其实还可以优化的，不过我很懒。

然后看图：

很明显如果我们有红线，那么蓝线和灰线可以直接删除掉。即一条线如果被包含，那么选包含它的线一定比选它优。通过这一步操作后，所有线段的关系都像绿线和红线一样了。即他们不相互包含。最后，我们得到了一些线段，他们的左端点排成升序后，右端点也是升序。

然后，我们继续贪心，看图：

显然如果我们选了红线那么下一条线一定选深红的线，因为前面已经保证了左端点和右端点都为升序，所以贪心是对的。然后这一步就是选一条右端点最远，而左端点与已选线段相交的线。

通过预处理，这个操作可以O(1)，如果不是很贪心（比如我），现在就可以枚举一个地方把环切成链，然后做出。

如果还要贪心点，可以标记一下在已枚举的线段中的最优决策里被选中的线段，下次不枚举它。

那么可以O(n)求出最优，当然，由于前面的快排已经O(nlogn)了。所以，时间复杂度为O(nlogn)。

CODE:

/*

PROG: corral

LANG: C++

ID: boleyn.2

*/

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-22

DESCRIPTION:

TITLE: Covering the Corral [Richard Peng, 2009]

CONTENT:

The cows are so modest they want Farmer John to install covers

around the circular corral where they occasionally gather. The

corral has circumference C (1 <= C <= 1,000,000,000), and FJ can

choose from a set of M (1 <= M <= 100,000) covers that have fixed

starting points and sizes. At least one set of covers can surround

the entire corral.

Cover i can be installed at integer location x_i (distance from

starting point around corral) (0 <= x_i < C) and has integer length

l_i (1 <= l_i <= C).

FJ wants to minimize the number of segments he must install. What

is the minimum number of segments required to cover the entire

circumference of the corral?

Consider a corral of circumference 5, shown below as a pair of

connected line segments where both ‘0’s are the same point on the

corral (as are both 1’s, 2’s, and 3’s).

Three potential covering segments are available for installation:

           Start   Length

      i     x_i     l_i

      1      0       1

      2      1       2

      3      3       3

        0   1   2   3   4   0   1   2   3  …

corral: +—+—+—+—+–:+—+—+—+- …

        11111               1111

            22222222            22222222

                    333333333333

            |………………|

As shown, installing segments 2 and 3 cover an extent of (at least)

five units around the circumference. FJ has no trouble with the

overlap, so don’t worry about that.

PROBLEM NAME: corral

INPUT FORMAT:

* Line 1: Two space-separated integers: C and M

* Lines 2..M+1: Line i+1 contains two space-separated integers: x_i

        and l_i

SAMPLE INPUT (file corral.in):

5 3

0 1

1 2

3 3

OUTPUT FORMAT:

* Line 1: A single integer that is the minimum number of segments

        required to cover all segments of the circumference of the

        corral

SAMPLE OUTPUT (file corral.out):

2

*/

#include <stdio.h>

 

const int MAXM=100000;

int C,M;

int x[MAXM],l[MAXM];

int answer;

int right[MAXM];

int f[MAXM];

 

void quick_sort(int L,int R)

{

     int x_mid=x[(L+R)>>1];

     int l_mid=l[(L+R)>>1];

     int i=L,j=R;

     while (i<=j)

     {

           while ((x[i]<x_mid)||(x[i]==x_mid&&x[i]+l[i]>x_mid+l_mid)) i++;

           while ((x[j]>x_mid)||(x[j]==x_mid&&x[j]+l[j]<x_mid+l_mid)) j–;

           if (i<=j)

           {

              int swap;

              swap=x[i];

              x[i]=x[j];

              x[j]=swap;

              swap=l[i];

              l[i]=l[j];

              l[j]=swap;

              i++;

              j–;

           }

     }

     if (L<j) quick_sort(L,j);

     if (i<R) quick_sort(i,R);

}

 

int main()

{

    freopen(“corral.in”,“r”,stdin);

    freopen(“corral.out”,“w”,stdout);

    scanf(“%d %d\n”,&C,&M);

    for (int i=0;i<M;i++)

        scanf(“%d %d\n”,&x[i],&l[i]);

   

    quick_sort(0,M-1);

   

    for (int i=0,j=0;j<M;)

    {

        x[i]=x[j];

        l[i]=l[j];

        j++;

        while ((x[i]+l[i]>=x[j]+l[j])&&(j<M)) j++;

        i++;

        if (j>=M) M=i;

    }

   

    //for (int i=0;i<M;i++)

    //    printf(“%d %d\n”,x[i],x[i]+l[i]);

   

    for (int i=M-1,j=M-1;i>=0;i–)

    {

        while ((x[j]>x[i]+l[i])&&(j>=0)) j–;

        right[i]=j;

    }

   

    answer=MAXM;

    for (int begin=M-1;;begin–)

    {

        if (x[begin]+l[begin]<C) break;

        int X=x[begin]+l[begin]-C;

        int L=x[begin]-X;

        if (L<=0)

        {

           answer=1;

           break;

        }

       

        //printf(“begin:%d\n”,begin);

        //printf(“X=%d X+L=%d\n”,X,X+L);

        f[begin]=1;

        for (int i=begin-1,j=begin;i>=0;i–)

        {

            //while (x[j]>x[i]+l[i]) j–;

            //printf(“i%d j%d\n”,i,j);

            f[i]=f[right[i]]+1;

            //f[i]=f[j];

            //for (int k=j;k>i;k–)

            //    if (f[i]>f[k])

            //       f[i]=f[k];

            //f[i]++;

           

            if (x[i]<=X)

            {

               if (answer>f[i]) answer=f[i];

               //printf(“begin:%d f[%d]=%d\n”,begin,i,f[i]);

               break;

            }

        }

    }

   

    printf(“%d\n”,answer);

   

    fclose(stdin);

    fclose(stdout);

    return 0;

}