codeforces 985C. Liebig's Barrels-白红宇

codeforces 985C. Liebig's Barrels

阅读量：4485 次

发布时间：2019-06-08

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

n表示桶的个数，k表示每个桶的木板数目，l表示任意两个桶中的最短木板的差值的上限。

思路比较明确，找出最短木板的长度记为 m，那么每个桶的最短木板的范围在[ m,m+l]之间。、

在计算和的时候，思路有点混乱，始终没有找到正确的方法。

其实可以这样想：

如果长度小于m+l的木板数目小于n，那么无解

如果正好等于，就是前n个木板的和

如果长度小于m+l的木板数目大于n，就需要跳过一些木板，同时要保证最后的和是最大的

针对第三种情况，枚举n个水桶，每个水桶最多跳过k-1个木块，同时保证剩下的范围在[ m,m+l ]之间的木板的个数可以分给剩下的水桶

int ptr=0;        for(int i=0;i
     
      n-i-1)ptr++;                else break;            }        }

非常简短巧妙的代码

整题的代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #define DEBUG(x) cout<<#x<<" = "<
               
                <
                
                 n-i-1)ptr++; else break; } } printf("%I64d\n",sum); }}