贪心。假设每个牛都有一块木板,则长度为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; }