工业园做网站的公司合肥今日头条最新消息

思路：如果用n^2复杂度暴力会超时。nlogn 可以，利用前缀和化简，提前存储某个位置前的每个石头搬运到该位置和每个石头后搬运到该位置的前缀和On最后直接输出 On。排序花 nlogn

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define w second
#define p first
const int N = 1e5+10;
typedef long long  LL;
PII q[N];
int n;
LL pre[N],nex[N];int main( ){cin>>n;for(int i=1;i<=n;i++){cin>>q[i].w>>q[i].p;}sort(q+1,q+1+n);LL s = 0;for(int i=2;i<=n;i++){s+=q[i-1].w;pre[i] = (q[i].p-q[i-1].p)*s+pre[i-1];}s = 0;for(int i=n-1;i>=1;i--){s+=q[i+1].w;nex[i] = (q[i+1].p-q[i].p)*s+nex[i+1];}LL ans = 1e18;pre[0]=0;nex[n]=0;for (int i = 1; i <= n; ++ i )ans = min(ans, pre[i] + nex[i]);cout<<ans<<'\n';return 0;
}