USACO Barn Repair

被婊到……
USACO的Greedy Algorithm說明文寫得根本不是Greedy Algorithm……
什麼求n = 5時先求n = 4的最佳解，害我想到DP去。
（因為n = 4的最佳解必定是n = 3的最佳解……根本就是從n = 1往上推的意思）

如果演算法正確還ok，
問題是DP的code到測資第5組就gg惹 =.=。
你說這不會讓人想殺人嗎？

其實也不用管什麼Greedy不Greedy的，
直接想作法還比較實際……
Greedy Algorithm這名詞真是抽象無比。

先對C做sort。
接著算出每個C之間的間距，一樣sort。
再計算只用1塊板子的長度Len，
當m = 1表示用1塊板子，Len就是答案。
m = 2時，Len要減去最大間距，
m = 3時，Len要減去最大間距與次大間距。
若m >= C，直接output C。
其實就這樣而已……

另外fopen本來就要fclose吧？
USACO的code從不做fclose，
無言。

盡信書不如無書。
一堆google別人想的解法還比USACO的好太多了 = =。

/*
ID: mythnc2
LANG: C
TASK: barn1
barn repair
2011/11/16 16:21:20   
*/
#include <stdio.h>
#include <stdlib.h>

#define MAXARY 200

int cmp(const void *, const void *);

int main (void)
{
    FILE *fin, *fout;
    int n, nc, i, sum;
    int ary[MAXARY], diff[MAXARY];

    fin = fopen("barn1.in", "r");
    fout = fopen("barn1.out", "w");

    fscanf(fin, "%d %*d %d", &n, &nc);
    for (i = 0; i < nc; i++)
        fscanf(fin, "%d", ary + i);

    if (n < nc) {
        qsort(ary, nc, sizeof(int), cmp);
        for (i = 0; i < nc - 1; i++)
            diff[i] = ary[i + 1] - ary[i] - 1;
        qsort(diff, nc - 1, sizeof(int), cmp);
        sum = ary[nc - 1] - ary[0] + 1;
        for (i = nc - 2; n > 1 ; i--, n--)
            sum -= diff[i];
        fprintf(fout, "%d\n", sum);
    }
    else
        fprintf(fout, "%d\n", nc);

    fclose(fin);
    fclose(fout);
    return 0;
}

/* cmp: function of qsort argument */
int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}