贪心 这道题相当于要求 原本有 y个 空隙 现在要求只有(m-1)个空隙

那肯定要填那些空隙比较小的 空隙

这样用贪心做一遍就可以了 选最小的几个就行了

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std ; 5  6 int m,c,s ; 7 int a[211],b[211] ;  8  9 int main() 10 {11     scanf("%d%d%d",&m,&s,&c) ;12     for(int i=1;i<=c;i++) scanf("%d",&a[ i ]) ;13     sort(a+1,a+c+1) ;14     int cnt = 0,y = 0  ; 15     for(int i=2;i<=c;i++) 16     {17         int x = a[i]-a[i-1] ; 18         if(x<=1) x = 2000000000 ; 19             else y++ ;20         x-- ;21         b[++cnt] = x ; 22     }23     24     sort(b+1,b+cnt+1) ;25     int ans = c ;26     for(int i=1;i<=y-(m-1);i++) 27         ans+=b[ i ] ;28     printf("%d",ans) ; 29     return 0 ;30 }