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

大家都是把一块木板从头铺到尾然后断开差最大的几个，但其实每个牛棚铺一块木板然后连上差最小的几个也行啊...... 弄一个diff数组 ~~装差~~ 放差 代码： ```cpp #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; } ```