明日方舟吧 关注:1,762,372贴子:81,943,695
  • 9回复贴,共1

吧里有没有玩过NOIP/ACM或者接触过编程OJ的,出道题给你们水水

只看楼主收藏回复

在遥远的泰拉世界,有个无良的博士,天天让手下干员加班工作。有一天,博士接到一个紧急请求,很长时间没法回罗德岛,于是他就想在回来的时候从制造站拿到最多的产品。已知他的舰上有M个三级制造站(可以进驻三个干员,且基础仓库容量为54),手下有N个增加仓库容量的干员,且这些干员在精力耗尽时也会保留增加仓库的技能。除此之外,博士手下没有任何加速制造的干员。为了达到生产最大化,博士希望所有的仓库容量都尽可能高,防止某些仓库爆满,另一些仓库仍然有空位。那么,你可以计算出在最优安排下,全舰仓库最小的制造站的容量最高可以达到多少吗?
INPUT
第一行输入两个数字M,N,表示三级制造站数量和可增加仓库的干员数量。
第二行输入N个数字,C1,C2……CN,表示每个干员可增加的仓库容量。
OUTPUT
对于每个测试样例,输出一个数字,表示全舰仓库最小的制造站最大可达到的容量。
SAMPLE INPUT
2 8
6 10 16 8 1 9 3 2
SAMPLE OUTPUT
79
(可以在第一个制造站安排加仓库数6,10,9的干员,第二个制造站安排加仓库数16,8,3的干员,那么制造站1可以加仓库25,制造站2可以加仓库27,外加基础的54仓库,全舰仓库最小的就是54+25=79容量,其他分配方法也不会让最小的仓库大于79。注意每个制造站最多只能安排三名干员)


IP属地:美国1楼2020-04-04 00:10回复
    啊这,排序+(n,3)的枚举?


    IP属地:北京来自Android客户端2楼2020-04-04 00:17
    收起回复
      先求平均值得出最小的仓库的一个上限然后从排序好的队列中进行暴力验算,直到出现第一个可行解并输出?


      IP属地:上海3楼2020-04-04 00:26
      回复
        二分答案


        来自Android客户端4楼2020-04-04 00:34
        回复
          数据范围呢


          来自Android客户端5楼2020-04-04 00:37
          收起回复
            排序+dp


            IP属地:北京6楼2020-04-04 00:46
            回复