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。

• 对于 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; // 更新到当前位置为止的总石头重量
}