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

2018-05-07 17:50:36


大家都是把一块木板从头铺到尾然后断开差最大的几个,但其实每个牛棚铺一块木板然后连上差最小的几个也行啊......

弄一个diff数组 装差 放差

代码:

#include <bits/stdc++.h>
using namespace std;
int m,s,c,ans,diff[300],a[300];
int main ()
{
    scanf("%d%d%d",&m,&s,&c);
    for (int i = 0;i < c;i++) scanf("%d",&a[i]);//读入
    ans = c;至少要放这么多
    sort(a,a + c);//排个序
    for (int i = 0;i < c - 1;i++) diff[i] = a[i + 1] - a[i] - 1;//算差
    sort(diff,diff + c - 1);//再次排序
    //for (int i = 0;i < c - 1;i++) printf("%d ",diff[i]); 调试用代码,请忽略
    int len = c,i = 0;
    while (len > m) //木板数不符合要求
    {
        len--;ans += diff[i++];
    }
    printf("%d",ans);
    return 0;
}