题解：P11376 [GESP202412 六级] 运送物资

N0_1 · 2024-12-11 12:46:05 · 题解

说明：

读题后分析易知，原题可以转换为求该表达式的最小值

其中 x_i 表示第 i 个站点的位置， p 表示两市之间的距离， a_i 和 b_i 见题目。

对该表达式化简可得

其中 2 \times \sum pb_i 为定值，原题转化为求 \sum x_i(a_i-b_i) 的最小值，令 dif_i 表示 a_i - b_i， 即求 \sum x_idif_i。根据初中数学知识，不难知道当最小 dif_i 与最大的 x_i 配对时，\sum x_idif_i 为最小值。

注意 code 的时候 x_i 有数量限制。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;

struct node {
    int x, num;
};
struct car {
    int a, b;
};
node a[N];
car b[N];

LL x[N], dif[N];

int main() {
    int n, m;
    LL p;
    cin >> n >> m >> p;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].num;
    for (int i = 1; i <= m; i++) cin >> b[i].a >> b[i].b, dif[i] = b[i].a - b[i].b;

    sort(a + 1, a + n + 1, [](node t, node f) {
        return t.x < f.x;
    });
    sort(dif + 1, dif + m + 1);

    int tpl = 1, tpr = n, dol = 1, dor = m;
    LL sum = 0;

    while (dol <= m && dif[dol] < 0) {
        if (a[tpr].num > 0) {
            sum += dif[dol] * a[tpr].x;
            dol ++;
            a[tpr].num --;
        } else {
            tpr --;
        }
    }

    while (dor >= dol) {
        if (a[tpl].num > 0) {
            sum += dif[dor] * a[tpl].x;
            dor --;
            a[tpl].num --;
        } else {
            tpl ++;
        }
    }
    sum *= 2;
    for (int i = 1; i <= m; i++) {
        sum += 2 * p * b[i].b;
    }

    cout << sum << '\n';
    // system("pause");
    return 0;
}