P11376 [GESP202412 六级] 运送物资 题解
tomAmy
·
·
题解
个人觉得是一道比较难的黄题。
凭直觉来讲：
-
按 p_j 从小到大对点排序。
-
对 a_i \ge b_i 的货车排序，依次匹配 p_j 小的点。
-
对 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)。
$$\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$ 应越大。
剩下的就是贪心模拟啦~
代码：
```cpp
#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;
}
``````
点个赞再走呗~