這題是一個(gè)比較簡(jiǎn)單的貪心題，不過如果不知道的話，可能會(huì)很unhappy了，因?yàn)檫@個(gè)是逆向來的，也就是如果你知道了用M塊木板覆蓋的消耗的話，那么你就可以算出用M-1塊木板覆蓋的最小覆蓋，方法就是在M塊木板中找相鄰的兩塊木板相差距離最小的，然后把這兩塊木板連起來，這樣的消耗一定是最小的（這個(gè)就不用證明了吧，很明顯的）。根據(jù)這個(gè)思路，可以比較容易的A掉這題，但是還有一些實(shí)現(xiàn)的細(xì)節(jié)下面看代碼吧。
對(duì)于樣例的覆蓋過程是
[3][4][6][8][14][15][16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14][15][16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15][16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16][17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25][26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26][27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30][31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40][41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40,41][42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40,41,42][43]
[3,4][6][8][14,15,16,17][21][25,26,27][30,31][40,41,42,43]
[3,4,6][8][14,15,16,17][21][25,26,27][30,31][40,41,42,43]
[3,4,6,8][14,15,16,17][21][25,26,27][30,31][40,41,42,43]
[3,4,6,8][14,15,16,17][21][25,26,27,30,31][40,41,42,43]
[3,4,6,8][14,15,16,17,21][25,26,27,30,31][40,41,42,43]

code
  6#include <iostream>
 7#include <string.h>
 8using namespace std;
 9/**//*結(jié)構(gòu)體村每個(gè)點(diǎn)的數(shù)據(jù)
10  其中data表示輸入的數(shù)據(jù)
11  left和right表示他的左右邊
12  有沒有連了其他的木板 
13 */ 
14typedef struct
15{
16    int data;
17    int left,right;
18}Node;
19Node node[202];
20bool b_barn[202];//b_barn[i]表示第i號(hào)牛棚有沒有被木板覆蓋 
21int m,s,c;//和題目中的一樣 
22void work()
23{
24      int f_start,f_end,dis;//dis表示最小距離
25      //f_start表示最小距離時(shí)的左邊的下標(biāo)
26      //f_end 表示最小距離時(shí)的右邊的下標(biāo)
27      int count = 0;//用來存最后的結(jié)果 
28      int t = c;//表示一開始用c塊木板，也就是一個(gè)牛棚一塊 
29      dis = 202;//最大距離，表示無窮 
30      while(t > m)
31        {
32            dis = 202;
33            for(int i = 1;i < c;i++)//循環(huán)數(shù)組，找相隔最小的，然后連上 
34              {//因?yàn)檫@樣“浪費(fèi)”的木板最少，也就是能達(dá)到最優(yōu)解 
35                  if(((node[i].data - node[i-1].data) < dis)&&(0 == node[i].left||0 == node[i-1].right))
36                    {//第一個(gè)判斷條件很好理解，第二個(gè)是表示他們以前沒連過，不然的話，
37                     //會(huì)一直找到第一個(gè)最小的 ,而忽略了后面的 
38                       dis = node[i].data - node[i-1].data;
39                       f_start = i-1;
40                       f_end = i;
41                      }
42              }
43            for(int i = node[f_start].data+1;i < node[f_end].data;i++)
44              {//將連起來的兩塊木板中間的都置為被覆蓋 
45                 b_barn[i] = true;
46              }
47            node[f_start].right = 1;//標(biāo)記，也就是這個(gè)點(diǎn)的右邊連了其他木板 
48            node[f_end].left = 1;//標(biāo)記，也就是這個(gè)點(diǎn)的左邊連了其他木板
49            t--;//表示木板數(shù)減少1 
50         }
51       for(int i = node[0].data;i < node[c-1].data+1;i++)
52        {
53             if(b_barn[i])//通過被標(biāo)記的數(shù)組來算最后的結(jié)果 
54                 count++;
55         }
56       printf("%d\n",count);
57}
58int cmp(const void *a,const void *b)
59 {
60      Node * c = (Node *)a;
61      Node * d = (Node *)b;
62      return c->data - d->data;
63}
64int main(void)
65{
66      freopen("barn1.in","r",stdin);
67      freopen("barn1.out","w",stdout);
68      scanf("%d %d %d",&m,&s,&c);
69      memset(b_barn,false,sizeof(b_barn));//初始化數(shù)組 
70      for(int i = 0;i < c;i++)
71       {
72          scanf("%d",&node[i].data);
73          node[i].left = node[i].right = 0;//初始化所有的都沒有連過 
74          b_barn[node[i].data] = true;    
75          
76        }
77      qsort(node,c,sizeof(node[0]),cmp);//先排序，使木板有序 
78      work();
79    return 0;
80}
81