USACO sec1.3 Barn Repair

問題の意味が分かりにくい.
番号は1 2 3です...Sの牛小屋、その中のC個は牛があって残りはなくて、今すべての牛小屋のガードレールはすべて大雨に降られて壊れて、牛小屋のガードレールを提供する商人は一定の数(M個)のガードレール(長さは勝手で、どれだけ長くて提供することができます)しか提供できなくて、moneyを節約するために、FJはすべての牛の小屋がすべて修理する前提の下で、必要なガードレールの全長を最小限に抑える(またはガードレールに囲まれた牛小屋の総数を最小限に抑える).
まずS<=Mであれば、完全にS個でいいので、要求を満たして最小限である.
S>Mであれば、牛を含まない牛小屋を大きなガードレールで囲む必要があります.牛を含まない牛小屋が含まれています.牛を含まない牛小屋の総数を最小限に抑えるには、同じガードレールの下の不連続な断片をできるだけ小さくして、欲張りな考えがあります.
迂回しすぎます.

/*

    PROG : barn1

    LANG : C++

*/



# include <cstdio>

# include <cstdlib>

# include <cstring>



int M, C, S, b[205];

char a[205];



int cmp(const void *x, const void *y)

{

    return *(int*)x > *(int*)y ? -1 : 1;

}



int main()

{

    freopen("barn1.in", "r", stdin);

    freopen("barn1.out", "w", stdout);

    

    int i, j, x, cnt, ans = 0, k;

    scanf("%d%d%d", &M, &S, &C);

    memset(a, 0, sizeof(a));

    for (i = 0; i < C; ++i) scanf("%d", &x), a[x] = 1;

    k = 0;

    i = 1;

    while (!a[i]) ++i; ans += i-1;

    j = S;

    while (!a[j]) --j; ans += S-j;

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

    {

        cnt = 0;

        while (i <= j && !a[i]) ++i, ++cnt;

        if (cnt) b[k++] = cnt;

    }

    if (k < M-1)

        printf("%d
", C);

    else

    {

        qsort(b, k, sizeof(int), cmp);

        for (i = 0; i < M-1; ++i) ans += b[i];

        printf("%d
", S-ans);

     }



     fclose(stdin);

     fclose(stdout);

      

    

    return 0;

}