贪心。假设每个牛都有一块木板,则长度为lenmax-lenmin。但是现在我们只要m块。所以我们要尽可能的减去最长的空隙,那么剩下来的才会是

最小的长度/所以首先按照牛棚之间的间隙排序,然后累加相减就可以了。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main()
{
    int m,s,c,i;
    int t[210],p[210]={0};
    scanf("%d%d%d",&m,&s,&c);
    for(i=0;i<c;i++)
        scanf("%d",&t[i]);
    sort(t,t+c);
    for(i=1;i<c;i++)
        p[i]=t[i]-t[i-1]-1;
    sort(p,p+c);
    int sum=0;
    for(i=c-1;i>=c-m+1&&i>=1;i--)
        sum+=p[i];
    printf("%d\n",t[c-1]-t[0]-sum+1);
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation