这题是一个比较简单的贪心题,不过如果不知道的话,可能会很unhappy了,因为这个是逆向来的,也就是如果你知道了用M块木板覆盖的消耗的话,那么你就可以算出用M-1块木板覆盖的最小覆盖,方法就是在M块木板中找相邻的两块木板相差距离最小的,然后把这两块木板连起来,这样的消耗一定是最小的(这个就不用证明了吧,很明显的)。根据这个思路,可以比较容易的A掉这题,但是还有一些实现的细节下面看代码吧。 对于样例的覆盖过程是 [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]
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) code 6 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) #include <iostream> 7 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) #include <string.h> 8 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) using namespace std; 9 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*结构体村每个点的数据 10 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 其中data表示输入的数据 11 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) left和right表示他的左右边 12 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 有没有连了其他的木板 13 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif) */ 14 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) typedef struct 15 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) { 16 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) int data; 17 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) int left,right; 18 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif) }Node; 19 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) Node node[202]; 20 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) bool b_barn[202];//b_barn[i]表示第i号牛棚有没有被木板覆盖 21 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) int m,s,c;//和题目中的一样 22 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) void work() 23 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) { 24 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) int f_start,f_end,dis;//dis表示最小距离 25 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) //f_start表示最小距离时的左边的下标 26 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) //f_end 表示最小距离时的右边的下标 27 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) int count = 0;//用来存最后的结果 28 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) int t = c;//表示一开始用c块木板,也就是一个牛棚一块 29 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) dis = 202;//最大距离,表示无穷 30 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) while(t > m) 31 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 32 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) dis = 202; 33 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) for(int i = 1;i < c;i++)//循环数组,找相隔最小的,然后连上 34 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {//因为这样“浪费”的木板最少,也就是能达到最优解 35 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) if(((node[i].data - node[i-1].data) < dis)&&(0 == node[i].left||0 == node[i-1].right)) 36 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {//第一个判断条件很好理解,第二个是表示他们以前没连过,不然的话, 37 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) //会一直找到第一个最小的 ,而忽略了后面的 38 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) dis = node[i].data - node[i-1].data; 39 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) f_start = i-1; 40 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) f_end = i; 41 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif) } 42 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif) } 43 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) for(int i = node[f_start].data+1;i < node[f_end].data;i++) 44 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {//将连起来的两块木板中间的都置为被覆盖 45 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) b_barn[i] = true; 46 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif) } 47 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) node[f_start].right = 1;//标记,也就是这个点的右边连了其他木板 48 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) node[f_end].left = 1;//标记,也就是这个点的左边连了其他木板 49 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) t--;//表示木板数减少1 50 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif) } 51 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) for(int i = node[0].data;i < node[c-1].data+1;i++) 52 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 53 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) if(b_barn[i])//通过被标记的数组来算最后的结果 54 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) count++; 55 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif) } 56 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) printf("%d\n",count); 57 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif) } 58 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) int cmp(const void *a,const void *b) 59 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) { 60 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) Node * c = (Node *)a; 61 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) Node * d = (Node *)b; 62 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) return c->data - d->data; 63 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif) } 64 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) int main(void) 65 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) { 66 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) freopen("barn1.in","r",stdin); 67 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) freopen("barn1.out","w",stdout); 68 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) scanf("%d %d %d",&m,&s,&c); 69 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) memset(b_barn,false,sizeof(b_barn));//初始化数组 70 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) for(int i = 0;i < c;i++) 71 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 72 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) scanf("%d",&node[i].data); 73 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) node[i].left = node[i].right = 0;//初始化所有的都没有连过 74 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) b_barn[node[i].data] = true; 75 76 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockEnd.gif) } 77 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) qsort(node,c,sizeof(node[0]),cmp);//先排序,使木板有序 78 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) work(); 79 ![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) return 0; 80 ![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockEnd.gif) } 81 ![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|