自动搬运

查看原文

来自洛谷，原作者为

	tomAmy 你好呀，有缘人～

搬运于2025-08-24 23:06:50，当前版本为作者最后更新于2024-12-11 23:19:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

个人觉得是一道比较难的黄题。

凭直觉来讲：

1. 按 $p_j$ 从小到大对点排序。

2. 对 $a_i \ge b_i$ 的货车排序，依次匹配 $p_j$ 小的点。

3. 对 $a_i < b_i$ 的货车排序，依次匹配 $p_j$ 大的点。

那么怎么对货车排序呢？

我好弱啊，看了题解才明白。

我们要对比同样的增减幅度下，哪个收益更大，就该配更大的增幅。

考虑货车 $x$ 与点 $u, v$：

若将货车 $x$ 分配给点 $u$，则行驶路程为 $2 a_x p_u + 2 b_x (X - p_u)$。

若将货车 $x$ 分配给点 $v$，则行驶路程为 $2 a_x p_v + 2 b_x (X - p_v)$。

$u \to v$，收益为

$$\begin{aligned} &\quad(2 a_x p_u + 2 b_x (X - p_u)) - (2 a_x p_v + 2 b_x (X - p_v))\\&= 2(a_x p_u + b_x (X - p_u) - a_x p_v - b_x (X - p_v))\\&= 2(a_x(p_u - p_v) + b_x (X - p_u - X + p_v))\\&=2(a_x(p_u - p_v) - b_x (p_u - p_v))\\&= 2(a_x - b_x)(p_u - p_v)\\&= 2(b_x - a_x)(p_v - p_u)\end{aligned} $$

若 $a_x\ge b_x$，要使收益越大，$a_x - b_x$ 应越大。

若 $a_x < b_x$，要使收益越大，$b_x - a_x$ 应越大。

剩下的就是贪心模拟啦~

代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;

struct Node1
{
	int p, c;
} e[N];

struct Node2
{
	int a, b;
} f[N], g[N];

int cntf, cntg;

bool cmp1(Node1 x, Node1 y)
{
	return x.p < y.p;
}

bool cmp2(Node2 x, Node2 y)
{
	return x.a - x.b > y.a - y.b;
}

bool cmp3(Node2 x, Node2 y)
{
	return x.b - x.a > y.b - y.a;
}

int main()
{
	int n, m, s;
	cin >> n >> m >> s;
	for (int i = 1; i <= n; i++)
		cin >> e[i].p >> e[i].c;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		if (x >= y) f[++cntf] = {x, y};
		else g[++cntg] = {x, y};
	}
	sort(e + 1, e + n + 1, cmp1);
	sort(f + 1, f + cntf + 1, cmp2);
	sort(g + 1, g + cntg + 1, cmp3);
	int now = 1;
	long long ans = 0;
	for (int i = 1; i <= cntf; i++)
	{
		if (e[now].c == 0) now++;
		ans += 2ll * f[i].a * e[now].p + 2ll * f[i].b * (s - e[now].p);
		e[now].c--;
	}
	now = n;
	for (int i = 1; i <= cntg; i++)
	{
		if (e[now].c == 0) now--;
		ans += 2ll * g[i].a * e[now].p + 2ll * g[i].b * (s - e[now].p);
		e[now].c--;
	}
	cout << ans << endl;
	return 0;
}

点个赞再走呗~