有走借dai宝10月13解压的吗

来源：蜘蛛抓取(WebSpider) 时间：2019-06-21 04:21 标签： 借dai宝10月13解压

版权声明：本文为博主原创文章未经博主允许不得转载。 /u/article/details/

小B来到了一个异世界成为了肥猪之王。
在这个异世界共有n种肥猪，编号分别为1...，n
小B希望集齐这n种肥猪。
1. 花费a[i]的金币召唤一只编号为i的肥猪
2. 花费x的金币使所有已召集的肥猪进化。
即编号为i的肥猪编号变成i+1特殊的，编号为n的肥猪编号变成1

请问小B最少要花多少金币才能集齐n种肥猪。    

第一行两个正整数n,x
接下来n行第i行一个正整数a[i]

假设要取 i-2 这个地方的代价来填充 i 这个位置，那麼在剩下两次右移时放入 i-2 这个位置即可如果要用原来的价值，那么就等全部右移完再放入

因此若已知共右移 x 次，那么每头猪的最小代價是确定的即：

枚举右移的次数 k，对于每个 k 算出最小代价然后使用线段树求区间最小值即可 




                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 借dai宝10月13解压 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐