题解：P11112 [ROI 2024 Day 1] 机器人物流

· · 题解

说句题外话：感觉这个题挺简单，至少是一道本蒟蒻能做出的题。

思路

因为每次完成订单和克隆机器人的花销是一样的，所以很容易想到是贪心，而不是 DP。

我们一定是要优先找到花费最小的订单去完成。

所以我们可以维护完成每个订单的代价（所需机器人的数量）cost 并将其排序，然后遍历 cost，计算最大利润 ans=\max\left \{i \times p-cost_{i} \times c \right \}。

PS：每完成一个订单，机器人公司会获得 p 个虚拟货币，p 即为完成每个订单的收益。

思路是这样，但是还有很多细节，具体看代码。

维护完成每个订单的代价（其实是所需机器人的数量）

用类似前缀和的方法维护 cost 数组：

int obstacle = 0;
for(int i = 1 ; i <= n + m ; ++i){
    LL t , h;
  scanf("%lld%lld" , &t , &h);
  if(t == 1)//障碍物
    obstacle += h;
  else//窗户
    cost[++cnt] = h + obstacle;//代价=窗户高+之前所有障碍物的高度
}
for(int i = 1 ; i <= m ; ++i)
  cost[i] -= 1;//初始即有一个机器人

计算答案

遍历 cost 即可。

LL ans = 0;//统计答案
for(int i = 1 ; i <= m ; ++i)
  ans = max(ans , i * p - cost[i] * c);//更新答案

再加上 cost 的排序，变量的定义，输入输出，头文件……AC 了！

code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n , m , c , p , cnt , cost[100010];//m个订单，所以开100000
int main(){
    scanf("%lld%lld%lld%lld" , &n , &m , &c , &p);
    int obstacle = 0;
    for(int i = 1 ; i <= n + m ; ++i){
        LL t , h;
        scanf("%lld%lld" , &t , &h);
        if(t == 1)//障碍物
            obstacle += h;
        else//窗户
            cost[++cnt] = h + obstacle;//代价=窗户高+之前所有障碍物的高度
    }
    for(int i = 1 ; i <= m ; ++i)
        cost[i] -= 1;//初始即有一个机器人
    sort(cost + 1 , cost + m + 1);//排序cost
    LL ans = 0;//统计答案
    for(int i = 1 ; i <= m ; ++i)
        ans = max(ans , i * p - cost[i] * c);//更新答案
    printf("%lld" , ans);
    return 0;
}

本蒟蒻的第一篇题解，希望能过吧。