带权中位数

嗯这个没什么好记录的 纯粹的结论 但是在某些情况下需要对问题进行拆分才能使用
假设一个数轴上有很多个点 这些点上都有人 要把所有人移动到同一个点上 并且所移动的距离最短
结论：将有人的点按大小排序 再进行前缀和 刚好超过总人数一半的那个点(假设总人数为sum 那么累加的人数>= sum / 2 时 就满足条件)即为所求的移动距离最短点 同时 假设每个点上只有一个人 那么只需要先排序 再求出中位数 就可以求出最短距离(求的方法因题而异)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 9;
using ll = long long;

struct P
{
  int pos, val, id;
}a[N];

int main ()
{
  ios::sync_with_stdio(0), cin.tie(0);
  int n;cin >> n;
  for (int i = 1;i <= n; ++ i) {
    cin >> a[i].pos;
    a[i].id = i;
  }
  ll sum = 0;
  for (int i = 1;i <= n; ++ i) {
    cin >> a[i].val;
    sum += a[i].val;
  }
  sort(a + 1, a + n + 1, [](const P &u, const P &v){
    return u.pos < v.pos;
  });
  ll res = 0;
  for (int i = 1;i <= n; ++ i)
  {
    res += a[i].val;
    if (res >= sum / 2) {
      cout << a[i].id << '\n';
      break;
    }
  }
}