双堆解法 类似于双堆求中位数 把前k小的数放进大根堆，大根堆的堆顶恰好就是第k小的数 剩下的数放进小根堆里 如果要插入一个x 如果x比大根堆堆顶大，就扔进小根堆不管它了 如果x比大根堆堆顶小，取出大根堆堆顶，把堆顶那个数放进小根堆，再把x放入大根堆 查找的时候，大根堆如果size是k，那么大根堆堆顶就是答案 下面是AC代码 #include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using i128 = __int128; int ma...

一种基于哈希表的解法 与二分的解法相似，把a[i] + b[j]的所有结果放到ab数组里面 不同的是，可以使用哈希表存储从c[i] + d[j] 用m.count(-ab)可以在最好是o(1)的时间复杂度下找到a+b+c+d = 0 但是题目数据好像卡了 哈希表解法最好的时间复杂度是O(n^2), 插入和查找一般是O(1) 在本题里哈希表比排序+二分慢了200ms 下面是ac代码 #include <bits/stdc++.h> using namespace std; using LL = long long; using I128 = __int128; using PII =...

一种前缀和的解法 假如我们并不知道中位数就是最优解 先看暴力枚举的思路 1-index数组a存储货仓的坐标 先给a排个序 for i := 1 to n a[i]距离左边货仓j: a[i] - a[j] 距离左边所有货仓就是 a[i] - (a[1] + a[2] +... + a[i - 1]) 不难发现，优化后面的sum(a[1], a[i - 1])可以用前缀和解决 即a[i]距它左边所有货仓的总距离就是a[i] - prefix[i - 1]; 同理a[i]的右侧就是(prefix[n] - prefix[i]) - (n - i) * a[i]; 看数据范围，很容易爆int，记得开l...