本文主要是介绍AtCoder Beginner Contest 127 F - Absolute Minima（对顶堆求动态中位数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：F - Absolute Minima (atcoder.jp)
题目大意，给出操作次数Q,完成Q次操作。
共两种操作：
操作1：输入 1 a b ,将 f(x) 替换为 f(x) + | x - a | + b;
操作2：输入 2，找出最小的 x 使得 f(x) 的值最小;
我们可以发现 | x - a | 可以抽象成位置 x 与位置 a 之间的距离，而 b 并不会受到 x 变化的影响。所以我们只需要距离已存在的位置 a 中距离其他点距离之和最小就可以了，很明显的可以看出 这个 a 是所有点中距离中位数最近的点。但是操作1会改变序列 a 的中位数，所以我们需要对顶堆来实现动态中位数的求解。
#include<bits/stdc++.h>
using namespace std;#define Pqueue priority_queue
#define lc p<<1
#define rc p<<1|1
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define fi first
#define se secondtypedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> PII;const int mod = 998244353;
const int N = 1e6 + 10;
const ld eps = 1e-9;
const ll inf = 0x3f3f3f3f;
const ll P = 131;/*****************************华丽的分割线*****************************/
priority_queue<ll, vector<ll>, greater<ll>> minq; //小根堆
priority_queue<ll> maxq; //大根堆
ll sum1, sum2; //大根堆中的总和与小根堆中的总和void insert(ll num) { //操作1if (minq.size() >= maxq.size() || maxq.empty()) {sum1 += num;minq.push(num);maxq.push(minq.top());sum1 -= minq.top();sum2 += minq.top();minq.pop();} else {sum2 += num;maxq.push(num);minq.push(maxq.top());sum2 -= maxq.top();sum1 += maxq.top();maxq.pop();}
}void solve() {ll q, tot = 0;cin >> q;while (q--) {int op;cin >> op;if (op == 1) {ll a, b;cin >> a >> b;insert(a);tot += b; //对b的迭加} else {ll siz = maxq.size() - minq.size(); //多出的x的个数cout << maxq.top() << " " << siz*maxq.top() + sum1 - sum2 + tot << "\n";}}
}int main() {IOSint T = 1;//cin>>T;while (T--)solve();return 0;
}/*
oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
x o
o _/_/_/_/ _/ x
x _/ o
o _/_/_/_/ _/ _/_/ _/_/ _/_/_/ _/_/ _/_/_/ _/_/ _/_/_/ _/ _/ _/ x
x _/ _/_/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ o
o _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/ _/_/ x
x _/ _/ _/_/ _/ _/ _/ _/_/_/ _/_/ _/ _/ _/ _/ _/ o
o _/ _/ _/ x
x _/ _/_/ _/ o
o x
xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
*/这篇关于AtCoder Beginner Contest 127 F - Absolute Minima（对顶堆求动态中位数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
