自动搬运

查看原文

来自洛谷，原作者为

	a_small_OIer 这个家伙不懒，但还是什么也没有留下

搬运于2025-08-24 23:04:19，当前版本为作者最后更新于2025-01-04 20:30:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

思路

因为每次完成订单和克隆机器人的花销是一样的，所以很容易想到是贪心，而不是 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;
}

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