题目：链接

题意

有n个石块，每一个位置有不同重量的石块，现在要进行n-1次操作，将所有的石块移动到同一个位置，特别注意，同一位置上可能有多个石头，一次操作只能移动一个石头。

思路

一开始想到直接利用中位数定理的结论，但是发现与题意有冲突，所以可以枚举移动到每一个位置上的花费，在算每一个位置上的花费时，可以采用前缀和的形式计算，比如说某位置的花费=某位置左侧位置上的花费+从左侧位置移动到该位置上的花费，右侧同理，注意重量的累加。

		pre[i] = pre[i-1];
        pre[i] += s * (a[i].p -a[i-1].p);
        s += a[i].w;

心得

不要一味的套公式！公式背后的推导要多思考。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef struct st
{
    int w;
    int p;
}St;
const int N = 1e5 + 10;
St a[N];
ll pre[N], nex[N];

bool cmp(St x, St y)
{
    return x.p < y.p;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;cin>>n;

    for(int i = 1; i <= n; i++) cin>>a[i].w>>a[i].p;
    
    sort(a + 1,a + 1 + n,cmp);

    ll s = 0;
    for(int i = 1; i <= n; i++)
    {
        pre[i] = pre[i-1];
        pre[i] += s * (a[i].p -a[i-1].p);
        s += a[i].w;
    }

    s = 0;
    for(int i = n; i >= 1; i--)
    {
        nex[i] = nex[i+1];
        nex[i] += s * (a[i+1].p - a[i].p);
        s += a[i].w;
    }

    ll ans = 1e18;
    for(int i = 1; i <= n; i++)
    {
        ans = min(ans, pre[i] + nex[i]);
    }

    cout<<ans;
    return 0;
}