洛谷題解：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代碼，
    */
}_[201];
int m,s,c;
bool cmp(node c,node d)
{
    return c.div>d.div;
}
int main()
{
    int ans=0;
    scanf("%d%d%d",&m,&s,&c);
    scanf("%d",&_[1].cow);_[1].div=0;
    for (int i=2;i<=c;i++)
    {
        scanf("%d",&_[i].cow);
        _[i].div=_[i].cow-_[i-1].cow;
    }
    sort(_+1,_+c+1,cmp);
    for (int i=m;i<=c;i++) ans+=_[i].div;
    ans+=m;
    printf("%d\n",ans);
    return 0;
}

這是一個50分代碼。很顯然，問題在於：認為輸入的編號一定是升序序列。所以，添加abs和sort，代碼為：  
代碼2（80分代碼）： 

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int cow,div;
    /*
    cow為該牛所占牛棚編號，
    div為該點與上一點差，
    _為這是一個WA代碼。
    */
}_[201];
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=0;
    scanf("%d%d%d",&m,&s,&c);
    scanf("%d",&_[1].cow);
    for (int i=2;i<=c;i++)
        scanf("%d",&_[i].cow);
    sort(_+1,_+c+1,cmp1);
    for (int i=2;i<=c;i++) _[i].div=abs(_[i].cow-_[i-1].cow);
    sort(_+1,_+c+1,cmp2);
    for (int i=m;i<=c;i++) ans+=_[i].div;
    ans+=m;
    printf("%d\n",ans);
    return 0;
}

這個代碼很容易被認為是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為上一點。
    */
}_[201];
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=0;
    scanf("%d%d%d",&m,&s,&c);
    if (m>=c) {printf("%d\n",c);return 0;}
    scanf("%d",&_[1].cow);_[1]._last=0;_[1]._this=1;
    for (int i=2;i<=c;i++)
        scanf("%d",&_[i].cow);
    sort(_+1,_+c+1,cmp1);
    for (int i=2;i<=c;i++) _[i].div=abs(_[i].cow-_[i-1].cow),_[i]._this=i,_[i]._last=i-1;
    sort(_+1,_+c+1,cmp2);
    for (int i=m;i<=c;i++) ans+=_[i].div;
    ans+=m;
    printf("%d\n",ans);
    return 0;
}