两个set维护k-1小|对顶堆-懒删除
lc3013两个set维护k-1小对顶堆-懒删除 数据流中的中位数class Solution {public:long long minimumCost(vectorint nums, int k, int dist) {k--;long long sum reduce(nums.begin(), nums.begin() dist 2, 0LL);multisetint L(nums.begin() 1, nums.begin() dist 2), R;auto L2R []() {int x *L.rbegin();sum - x;L.erase(L.find(x));R.insert(x);};auto R2L []() {int x *R.begin();sum x;R.erase(R.find(x));L.insert(x);};while (L.size() k) {L2R();}long long ans sum;for (int i dist 2; i nums.size(); i) {// 移除 outint out nums[i - dist - 1];auto it L.find(out);if (it ! L.end()) {sum - out;L.erase(it);} else {R.erase(R.find(out));}// 添加 inint in nums[i];if (in *L.rbegin()) {sum in;L.insert(in);} else {R.insert(in);}// 维护大小if (L.size() k - 1) {R2L();} else if (L.size() k 1) {L2R();}ans min(ans, sum);}return ans;}};
)
