(贪心) $O(n^2)$
找出最大的(n-1)个间隔 ,然后减去即可 ;
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210 ;
int a[N] ;
int main(){
int n , s , c ; cin >> n >> s >> c ;
for(int i=1;i<=c;i++){
cin >> a[i] ;
}
if(n>=c){
cout << c << endl ;
return 0 ;
}
sort(a+1,a+1+c) ;
int ans = a[c] - a[1] + 1 ;
vector<int> b ;
for(int i=2;i<=c;i++){
b.push_back(a[i]-a[i-1]-1) ;
}
sort(b.begin(),b.end(),greater()) ;
n-- ;
for(int i=0;i<n;i++){
ans -= b[i] ;
}
cout << ans << endl ;
}