P1209 [USACO1.3]修理牛棚 Barn Repair

链接：P1209

---------------------------------------------------

这道题是一道贪心+排序的题目

从样例就可以知道，牛棚的输入并不一定有序，我们要先排序

---------------------------------------------------

然后考虑贪心，假如有无限多的木板，我们只要在每个牛棚前放一块就可以了。

这样就可以让总长度最小。

但是木板有限，而且如上放的木板都是不能省略的，但是我们可以把两块木板拼起来！

这样就可以减少木板总数了。然后贪心的考虑一下，怎样合并（填满空隙）最优？

能少放就少放呗。

至此，这道题的思路已经完备了。

对编号排序，然后建立差分数组，然后对查分数组排序，然后从小大大每次给答案加上其中一个元素

就相当于我们合并了他们（总木板数-1）

最后输出。

-----------------------------------------------

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int p;
int num[1000];
int c[100001];
int m,s,n;
int ans;
int a;
int main(){
    cin>>m>>s>>n;
    for(int i=1;i<=n;++i)
    cin>>num[i];
    sort(num+1,num+n+1);
    for(int i=2;i<=n;++i)
    c[++p]=num[i]-num[i-1]-1;
    sort(c+1,c+1+p);
    a=n-m;
    ans=n;
    for(int i=1;i<=a;++i)
    ans+=c[i];
    cout<<ans;
    return 0;
}

发送评论编辑评论

发送评论 编辑评论

发送评论编辑评论