USACO SEC.1.3 No.2 Barn Repair-白红宇

USACO SEC.1.3 No.2 Barn Repair

阅读量：4709 次

发布时间：2019-06-10

本文共 1487 字，大约阅读时间需要 4 分钟。

题意：约翰的牛棚损坏了需要修补，每个牛棚的宽度是一样的，一共有S个牛棚，供应商能够提供任意长度的木板（一个单位木板

覆盖一个牛棚），但总共最多有M个木板，现在牛棚里面还有C头牛，下面C行是每头牛的牛棚的位置。

寻找一种方案，使得总共的木板长度最短，覆盖所有的牛。

核心：

理解题意，条件限制：

①最多M个木板

②寻找最小的总木板长度

因为有C头牛，所以总木板长度最小就为C，问题转化为，增加覆盖某些牛棚，那么长度增加对应的长度，同时满足

木板块数不超过M

贪心的思路：找出空白的牛棚位置和数目例如 34_6_8_14...

那么第一个空白为7，连续空白为1，第三个空白为 [9,13]长度为5

原始状态下有X个空白（X+1个木板快）每填充一个空白，X减少一个，那么优先选择空白长度小的空白（增加总长度少）

直到木板块数不再超过M为止

注意：题目条件中没有说明有牛的牛棚数是顺序输入的

/*ID: lsswxr1PROG: barn1LANG: C++*/#include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       using namespace std;///宏定义const int INF = 1000000000;const int MAXN = 215;const int maxn = MAXN;///全局变量 和 函数#define USACO#ifdef USACO#define cin fin#define cout fout#endif//int blankSeg[maxn];int src[maxn];int M, S, C;int main(){#ifdef USACO ofstream fout ("barn1.out"); ifstream fin ("barn1.in");#endif ///变量定义 while (cin >> M >> S >> C) { int blanks = 0, totLen = C; for (int i = 0; i < C; i++) { cin >> src[i]; } sort(src, src + C); for (int i = 1; i < C; i++) { if (src[i] - src[i - 1] != 1) { blankSeg[blanks++] = src[i] - src[i - 1] - 1; } } int pos = 0, sum = blanks + 1; if (sum > M) sort(blankSeg, blankSeg + blanks); while (sum > M) { //消除一个空白 totLen += blankSeg[pos]; pos++; sum--; } cout << totLen << endl; } ///结束 return 0;}

转载于:https://www.cnblogs.com/rayforsure/p/3443530.html

你可能感兴趣的文章