解题思路
贪心,反向考虑没有木板的数量,选取最大min(m-1,n-1)个的间距
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=310;
int a[N];
vector<int> seq;
int m,total,n;
int main()
{
cin>>m>>total>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
// for(int i=1;i<=n;i++)
// cout<<a[i]<<" ";
for(int i=1;i+1<=n;i++)
{
seq.push_back(a[i+1]-a[i]-1);
}
sort(seq.begin(),seq.end(),greater<int>());
int front=a[1]-1,back=total-a[n];
total=total-(front+back);
for(int i=0;i<min(m-1,n-1);i++)
total-=seq[i];
cout<<total;
return 0;
}