GYM103660H.Distance

GYM103660H.Distance 题目思路

定义 d i s t ( l , r , x ) dist(l, r, x) dist(l,r,x)为点 x x x到区间 [ l , r ] [l, r] [l,r]的距离(如果包含则距离为 0 0 0)。求 x x x使得 ∑ i = 1 k d i s t ( l i , r i , x ) \sum^k_{i = 1} dist(l_i, r_i, x) ∑i=1k​dist(li​,ri​,x)最小。

不难发现，实际上就是对于给定的一堆区间，寻找一个竖线，使之穿过的区间尽可能地多，且距离未穿过的区间的距离尽可能小。考虑如何处理未穿过的区间：

• 初始我们插入一个区间，此时轴位于区间内，左右堆各插入一个端点；
• 对于新插入的区间，如果右端点比当前左侧最右端更靠左，说明轴应该往左移动，使之穿过新插入的区间；
• 如果新插入的区间，如果左端点比当前右侧最左端更靠右，说明轴应该向右移动，使之穿过新插入的区间；
• 否则，轴不需要移动，因为左右两侧队列处于平衡状态。那么左右端点分别插入左右队列即可。

Code

#include 
#pragma gcc optimize(2)
#define int long long 
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;

priority_queue leftq;
priority_queue rightq;


inline void solve(){
    int n = 0, ans = 0; cin >> n;
    leftq.emplace(-INT_MAX);
    rightq.emplace(INT_MAX);
    for(int i = 1; i > l >> r;
        if(r  rightq.top()){
            ans += l - rightq.top();
            leftq.emplace(rightq.top()); rightq.pop();
            rightq.emplace(l), rightq.emplace(r);
        } else {
            leftq.emplace(l), rightq.emplace(r);
        }
        cout