陕西建设厅网站wordpress 分类文章

思路：如果用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;
}