问题描述：

解题思路：

        官方：

        注意点：

        1.直观方法无法使用，因为其时间复杂度为O(n2)。带入题目数据n最大为1e5则时间复杂度为1e10，超过了运行限制（默认1e8）。

        2.pair不会自动排序，规则仍遵循sort()。pair放入数据需要建立pair类型的数组pair<int, int>a[]

        3.如何实现pre[]和nex[]：使用前缀和的算法，原本的a[i]需要换成对应题目要求

        假设有三块石头且已排序，下图前者的操作等同于后者，因此前缀和的实现个根据前者

    

        前者的实现逻辑如下：

        

        上图的逻辑为（1.）A到B的费用，即pre[2]（2.）费用为AB重量之和乘AB与C的距离

      （3.）将1和2的费用相加，即总费用pre[2]+s*(c.x - b.x)，s为A.y+b.y

题解：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
pair<int, int> p[N];//***
#define x   first   
#define y   second//表示y的别名为first。此处操作不能使用using，因为非结构类型起别名
using ll = long long;
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 + n + 1);
	
	ll s = 0;
	for(int i = 1; i <= n; i++)
	{
		pre[i] = pre[i-1] + s * (p[i].x - p[i-1].x);
		s += p[i].y;
	}
	
	s = 0;
	for(int i = n; i >= 1; i--)//**i--
	{
		nex[i] = nex[i+1] + s * (p[i+1].x - p[i].x);
		s += p[i].y;
	}
	
	ll res = 1e18;//函数内不可以定义超过1e5的数组，但可以定义很大的数字 
	for(int i = 1; i <= n; i++)
	{
		res = min(res, pre[i] + nex[i]);//注意min只能同类型比较，所以ll pre[]
	}
	
	cout << res;
	
	return 0; 
}

知识点：前缀和