OJ3829大石头的搬运工
题目：
在一款名为”大石头的搬运“的游戏中，玩家需要操作一排 n 堆石头，进行 n -1 轮游戏。每一轮，玩家可以选择一堆石头，并将其移动到任意位置。在n-1轮移动结束时，要求将所有的石头移动到一起(即所有石头的位置相同)即为成功。移动的费用为石头的重量乘以移动的距离。例如，如果一堆重量为2的石头从位置3移动到位置5，那么费用为 2x(5 -3)= 4。 请计算出所有合法方案中，将所有石头移动到一起的最小费用。 可能有多堆石头在同一个位置上，但是一轮只能选择移动其中一堆。
输入格式:
第一行一个整数 n，表示石头的数量。 接下来 几 行，每行两个整数 wi和 pi，分别表示第i个石头的重量和初始位置.
输出格式 :
输出一个整数，表示最小的总移动费用。
数据范围
对于 20%的测试样例，1<=n<=10^3。
对于100%的测试样例，1<=n<=10^5，1<=wi,pi<=10^6。
解题思路：
首先，我们需要明白在这个问题中，每一次移动的石头的位置并不影响后续的移动，也就是说，无论我们怎么移动石头，最后的总费用只依赖于每个石头最后的位置，而与移动的顺序无关。这个性质使得我们可以逐一考虑每个石头最后的位置，并比较得出最小的总费用。
然后，我们需要分析一下如何计算每一种放置石头的方式的总费用。一种直观的方法是，对于每个石头，我们都计算它被移动到目标位置的费用，然后将这些费用加总。但这样的计算方式在本题的数据范围下是无法接受的。我们需要寻找一种更优的方法。
这里，我们可以运用前缀和的思想。考虑到石头移动的费用与其重量和距离有关，我们可以先将石头按位置排序，然后计算每个石头移动到任一位置的费用，再利用前缀和的方法将这些费用累加起来。具体地，我们可以定义两个数组pre和nex，其中pre[i]表示前i个石头都移动到第i个石头的位置的总费用，nex[i]表示第i个石头之后的所有石头都移动到第i个石头的位置的总费用。这样，对于每个石头，我们就可以在0(1)的时间内算出所有石头都移动到它的位置的总费用。
时间复杂度分析
整个过程中，排序的时间复杂度是O(nlogn)，计算pre和 nex的时间复杂度是O(n)，查找pre + nex的最小值的时间复杂度是0(n)，所以总的时间复杂度是 O(n logn)。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+9;
#define x first
#define y second
typedef long long ll;
pair<int,int>p[N];
ll pre[N],nex[N];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>p[i].y>>p[i].x;sort(p+1,p+1+n);ll s=0;for(int i=1;i<=n;i++){pre[i]=pre[i-1];pre[i]+=s*(p[i].x-p[i-1].x);s+=p[i].y;}s=0;for(int i=n;i>=1;i--){nex[i]=nex[i+1];nex[i]+=s*(p[i+1].x-p[i].x);s+=p[i].y;}ll ans=1e18;for(int i=1;i<=n;i++){ans=min(ans,pre[i]+nex[i]);}cout<<ans<<endl;return 0;
}当输入为：
3
2 3
3 1
1 5输出为：
8过程解释：
当我们在计算 pre 数组的时候：
-
对于
i = 1:- 之前没有石头，所以
pre[1] = 0。 - 总重量更新为
s = 3（因为第一堆石头重量为3）。
- 之前没有石头，所以
-
对于
i = 2:- 我们需要把第一堆石头从位置1搬运到位置3，花费为
3 * (3 - 1) = 6。 pre[2]就变成之前的pre[1]加上新花费，也就是0 + 6 = 6。- 总重量
s现在变成3 + 2因为另外一堆石头重2，所以s = 5。
- 我们需要把第一堆石头从位置1搬运到位置3，花费为
-
对于
i = 3:- 现在我们把之前所有石头（总重量
s = 5）从位置3搬运到位置5，花费为5 * (5 - 3) = 10。 pre[3]就是之前的pre[2]加上这个新花费，也就是6 + 10 = 16。- 最后更新总重量
s，加上最后一堆石头重1，所以s = 6。
- 现在我们把之前所有石头（总重量
pre数组的值反映的是把所有石头搬到当前位置得到的累计成本。
然后，我们需要再计算 nex 数组，它储存的是从最右侧开始往左搬运到当前位置的累计成本。最后，程序遍历所有石头位置，对于每一个位置计算 pre[i] + nex[i]，也就是把所有石头搬到当前位置的总成本（往左和往右的成本之和）。最小的一个总成本就是我们要求的答案。
注：这样写也是可以的
for (int i = 1; i <= n; ++i)
{pre[i] = pre[i - 1] + s * (q[i].x - q[i - 1].x); // 合并了继承和添加搬运成本的步骤s += q[i].y; // 更新到当前位置为止的总石头重量
}