P11112 [ROI 2024] 机器人物流 (Day 1)题目背景翻译自 ROI 2024 D1T1。在 ROI 2224 举办之时一群能够克隆自身的机器人负责送货。人们不用出门可以直接通过窗户拿到货物。最开始只有一个送货机器人。在任何时候最上面的机器人可以在自己上方克隆出一个或多个新的机器人形成一个“机器人柱”。每个机器人的高度等于一层楼。在送货过程中机器人柱会沿着宿舍楼从左到右移动。机器人的数据库中包含了订单列表每个订单都指定了一个需要送货的窗户。当机器人队列经过一个窗户时如果队列中有机器人位于窗户所在的高度则可以直接完成送货。在移动过程中机器人柱可能会碰到障碍物。碰到障碍物后只有位于障碍物高度上方的机器人能够继续移动。这些机器人在经过障碍物后会立刻重新排成一个机器人柱并且可以继续移动、克隆和完成送货任务。障碍物和窗户之间的距离足够大因此机器人在经过障碍物时不会同时经过窗户。题目描述每完成一个订单机器人公司会获得p pp个虚拟货币而克隆一个新机器人的成本是c cc个虚拟货币。最终利润等于订单配送的总收入减去所有机器人克隆的总成本。公司希望最大化利润。请你确定公司可以获得的最大利润。公司不需要完成所有订单且机器人可以在任何时候停止送货。输入格式第一行包含四个整数n , m , c , p n, m, c, pn,m,c,p0 ≤ n , m ≤ 100000 0 \le n, m \le 1000000≤n,m≤1000001 ≤ c , p ≤ 1000000 1 \le c, p \le 10000001≤c,p≤1000000分别表示障碍物的数量、订单的数量、克隆一个机器人的成本和每个订单的配送收入。接下来的n m n mnm行描述了障碍物和窗户的详细信息按从左到右的顺序给出。每行包含两个整数t i t_iti​和h i h_ihi​1 ≤ t i ≤ 2 1 \le t_i \le 21≤ti​≤21 ≤ h i ≤ 1000000 1 \le h_i \le 10000001≤hi​≤1000000其中t i t_iti​表示对象的类型1 11为障碍物2 22为窗户h i h_ihi​表示障碍物的高度或窗户所在的楼层。保证有n nn个障碍物剩余m mm个为窗户。输出格式输出一个整数表示可以获得的最大利润。输入输出样例 #1输入 #12 3 2 6 1 2 2 3 1 1 2 6 2 2输出 #14输入输出样例 #2输入 #21 3 1 5 2 2 2 1 1 9 2 1输出 #29说明/提示样例1 11解释以下是订单配送的最佳策略之一如果选择配送到第二个窗户不会增加公司的利润。样例2 22解释只需要克隆一次机器人用来配送到第一个窗户因为这个新克隆的机器人可以继续用来配送到第二个窗户。为了配送到第三个窗户而进行额外的克隆在经济上是不划算的。下面是各个子任务的分值和特殊性质表格。全部数据范围见输入格式。子任务分值特殊性质1 1124 2424n ≤ 100 , m ≤ 100 , h i ≤ 100 n\le100,m\le100,h_i\le100n≤100,m≤100,hi​≤1002 2212 1212n 0 n0n03 3314 1414n 1 n1n14 4415 1515m 1 m1m15 5517 1717c 1 , p 10 6 c1,p10^6c1,p106且障碍物高度均为1 116 6618 1818无C实现#includebits/stdc.husingnamespacestd;typedeflonglongLL;LL n,m,c,p,cnt,cost[100010];//m个订单所以开100000intmain(){scanf(%lld%lld%lld%lld,n,m,c,p);intobstacle0;for(inti1;inm;i){LL t,h;scanf(%lld%lld,t,h);if(t1)//障碍物obstacleh;else//窗户cost[cnt]hobstacle;//代价窗户高之前所有障碍物的高度}for(inti1;im;i)cost[i]-1;//初始即有一个机器人sort(cost1,costm1);//排序costLL ans0;//统计答案for(inti1;im;i)ansmax(ans,i*p-cost[i]*c);//更新答案printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容