蓝桥杯省赛无忧 编程10 大石头的搬运工

#include <bits/stdc++.h>
using namespace std;
// 创建一个结构体来保存石头的重量和位置
struct Stone {
    int weight;
    int position;
};
int main() {
    int n;
    cin >> n;
    vector<Stone> stones(n);
    for (int i = 0; i < n; i++) {
        cin >> stones[i].weight >> stones[i].position;
    }
    // 按位置排序所有石头
    sort(stones.begin(), stones.end(), [](const Stone &a, const Stone &b) {
        return a.position < b.position;
    });
    // 计算加权中位数
    long long totalWeight = 0;
    for (const auto &stone : stones) {
        totalWeight += stone.weight;
    }
    long long halfWeight = 0;
    int medianPos = 0;
    for (const auto &stone : stones) {
        halfWeight += stone.weight;
        if (halfWeight * 2 >= totalWeight) {
            medianPos = stone.position;
            break;
        }
    }
    // 计算总费用
    long long cost = 0;
    for (const auto &stone : stones) {
        cost += static_cast<long long>(abs(stone.position - medianPos)) * stone.weight;
    }
    cout << cost << endl;
    return 0;
}
}

解决一个优化问题：找到一个目标位置，将所有给定的石头移动到这个位置，使得总移动费用最小。代码通过排序和计算加权中位数来实现这一目标。
代码分析：

struct Stone {
    int weight;
    int position;
};

定义了一个结构体Stone来存储每堆石头的重量（weight）和位置（position）。

int main() {
    int n;
    cin >> n;
    vector<Stone> stones(n);
    for (int i = 0; i < n; i++) {
        cin >> stones[i].weight >> stones[i].position;
    }

在main函数中，首先定义了一个整数变量n来接收用户输入的石头数量。然后创建了一个vector容器stones来存储所有的石头信息。使用for循环读取每堆石头的重量和位置，并将这些信息存储在stones向量中。

    sort(stones.begin(), stones.end(), [](const Stone &a, const Stone &b) {
        return a.position < b.position;
    });

这行代码使用sort函数和一个匿名函数（也称为lambda表达式）来对stones向量按石头的位置进行排序。

    long long totalWeight = 0;
    for (const auto &stone : stones) {
        totalWeight += stone.weight;
    }
    long long halfWeight = 0;
    int medianPos = 0;
    for (const auto &stone : stones) {
        halfWeight += stone.weight;
        if (halfWeight * 2 >= totalWeight) {
            medianPos = stone.position;
            break;
        }
    }

这部分代码计算了所有石头重量的总和totalWeight。然后通过遍历排序后的石头，累加重量直到达到或超过总重量的一半来找出中位数位置。这是因为，想要最小化距离总和，一个点最好是处在所有点的加权中位数位置。

    long long cost = 0;
    for (const auto &stone : stones) {
        cost += static_cast<long long>(abs(stone.position - medianPos)) * stone.weight;
    }

    cout << cost << endl;
    return 0;
}

最后，代码通过遍历每堆石头，计算将其移动到加权中位数位置的费用，并且累加起来得到总费用cost。使用abs函数来获取距离的绝对值，确保计算出的费用总是正数。由于位置和重量都可能是很大的数，所以使用long long类型来避免整数溢出。最后输出总费用并结束程序。