题目链接

solution：

按题目随便假设找到了一个x，它的位置的ap，属性bp

看下图

$$$$$$$$$$$$$$$$|||||P &&&&&&&&&&&&&&&

$：ap前，即ai<ap

&：ap后，即ai>ap

|：ap同，即ai==ap

显然要求解下面的式子

sigma 1~n (ai-x)*bi

前:(x-a1)*b1+(x-a2)*b2+(x-a3)*b3+……+(x-ap)*bp;

后:(ap+1-x)*bp+1+(ap+2-x)*bp+2+……+(an-x)*bn

前：b1x-a1b1+b2x-a2b2+b3x-a3b3+……+bpx-apbp

后：ap+1 * bp+1 - bp+1x + ap+2 * bp+2 - bp+2x +…..+ an*bn - bnx

(b1+b2+..+bp)x-(a1b1+a2b2+a3b3+…+apbp) （１）

(ap+1*bp+1+ap+2*bp+2+…+an*bn)-(bp+1*bp+2+…+bn)x （２）

为了使S最小

四个∑可以前缀后缀预处理Ｏ（１）查询

for循环用min确定要找的x就行了，也就是答案

显然数据并非有序，而我又有序的推证，所以要对数据排序

总最高复杂度就是排序nlogn

O（ｎ(ｌｏｎｇ+q) ）q常数

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define int unsigned long long
int n;
struct node{
    int a,b;
    bool operator < (const node & x) const {
        return a<x.a;
    };
}sky[N];
int sum1[N],sum2[N];
 main() {
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&sky[i].a);
    for(int i=1;i<=n;i++) scanf("%d",&sky[i].b);
    sort(sky+1,sky+1+n);
    for(int i=1;i<=n;i++) sum1[i]=sky[i].b+sum1[i-1],sum2[i]=sum2[i-1]+sky[i].a*sky[i].b;
    int ans=LLONG_MAX;
    for(int i=1;i<=n;i++) {
        int x=sky[i].a;
        int temp=0;
        temp=(sum1[i]-sum1[n]+sum1[i])*x;
        temp+=(sum2[n]-sum2[i]-sum2[i]);
        ans=min(ans,temp);
    }
    cout<<ans;
    return 0;
}