洛谷题解：P1209 【[USACO1.3]修理牛棚 Barn Repair】

原题传送门：https://www.luogu.org/problemnew/show/P1209

首先，这是一道贪心题。  
我们先来分析它的贪心策略。  
例如，样例：  
4 50 18  
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43  
它们之间的差是：  
1 2 2 6 1 1 1 4 4 1 1 3 1 9 1 1 1  
既然我们要让木板长度最小，那么我们就得空出前m-1个最大的区域，把其他区域累加，再加上一个m（例如3~8的差是8-3=5，而实际木板长度为8-3+1=6，每个木板都多一个，那么m个木板会多出m个）。  
代码1（50分代码）：

#include <bits/stdc++.h>

using namespace std;

struct node

{

    int cow,div;

    /*

    cow为该牛所占牛棚编号，

    div为该点与上一点差，

    _为这是一个WA代码，

    */

}_[];

int m,s,c;

bool cmp(node c,node d)

{

    return c.div>d.div;

}

int main()

{

    int ans=;

    scanf("%d%d%d",&m,&s,&c);

    scanf("%d",&_[].cow);_[].div=;

    for (int i=;i<=c;i++)

    {

        scanf("%d",&_[i].cow);

        _[i].div=_[i].cow-_[i-].cow;

    }

    sort(_+,_+c+,cmp);

    for (int i=m;i<=c;i++) ans+=_[i].div;

    ans+=m;

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

    return ;

}

这是一个50分代码。很显然，问题在于：认为输入的编号一定是升序序列。所以，添加abs和sort，代码为：  
代码2（80分代码）：

#include <bits/stdc++.h>

using namespace std;

struct node

{

    int cow,div;

    /*

    cow为该牛所占牛棚编号，

    div为该点与上一点差，

    _为这是一个WA代码。

    */

}_[];

int m,s,c;

bool cmp1(node c,node d)

{

    return c.cow<d.cow;

}

bool cmp2(node c,node d)

{

    return c.div>d.div;

}

int main()

{

    int ans=;

    scanf("%d%d%d",&m,&s,&c);

    scanf("%d",&_[].cow);

    for (int i=;i<=c;i++)

        scanf("%d",&_[i].cow);

    sort(_+,_+c+,cmp1);

    for (int i=;i<=c;i++) _[i].div=abs(_[i].cow-_[i-].cow);

    sort(_+,_+c+,cmp2);

    for (int i=m;i<=c;i++) ans+=_[i].div;

    ans+=m;

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

    return ;

}

这个代码很容易被认为是AC代码，其实不然。例如，测试点6，出现了m比c大的情况。那么它肯定不能用m个木板去覆盖。这种时候，我们只要在每个点上都摆一个长度为1的木板就行了，或者说，木板总长即为牛的只数。所以，代码如下：  
代码3（100分代码）：

//本题解由姆洋题解®提供。姆洋题解，蒟蒻们的题解。

#include <bits/stdc++.h>

using namespace std;

struct node

{

    int cow,div,_this,_last;

    /*

    cow为该牛所占牛棚编号，

    div为该点与上一点差，

    _this为该点，_last为上一点。

    */

}_[];

int m,s,c;

bool cmp1(node c,node d)

{

    return c.cow<d.cow;

}

bool cmp2(node c,node d)

{

    return c.div>d.div;

}

int main()

{

    int ans=;

    scanf("%d%d%d",&m,&s,&c);

    if (m>=c) {printf("%d\n",c);return ;}

    scanf("%d",&_[].cow);_[]._last=;_[]._this=;

    for (int i=;i<=c;i++)

        scanf("%d",&_[i].cow);

    sort(_+,_+c+,cmp1);

    for (int i=;i<=c;i++) _[i].div=abs(_[i].cow-_[i-].cow),_[i]._this=i,_[i]._last=i-;

    sort(_+,_+c+,cmp2);

    for (int i=m;i<=c;i++) ans+=_[i].div;

    ans+=m;

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

    return ;

}

洛谷题解：P1209 【[USACO1.3]修理牛棚 Barn Repair】的相关教程结束。