GYM103660H.Distance

GYM103660H.Distance

题目思路

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

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

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

Code

#include <bits/stdc++.h>
#pragma gcc optimize(2)
#define int long long 
#define endl '\n'
using namespace std;

const int N = 1e5 + 10;

priority_queue<int, vector<int>, less<int>> leftq;
priority_queue<int, vector<int>, greater<int>> rightq;


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

}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}