[C++] 純文本查看 復制代碼
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
ll sum=0,sps=0,spl=0;
priority_queue<int> ps;
priority_queue<int,vector<int>,greater<int>> pl;
for(int i=0;i<n;i++)
{
ll l,r;
cin>>l>>r;
sum+=r-l;
sps+=l;
spl+=r;
ps.push(l);
pl.push(r);
while(ps.top()>pl.top())
{
pl.push(ps.top());
sps-=ps.top();
spl+=ps.top();
ps.pop();
ps.push(pl.top());
spl-=pl.top();
sps+=pl.top();
pl.pop();
}
ll mid=ps.top(); //中位數
ll sdis=mid*ps.size()-sps; //和ps中所有點的距離
ll ldis=spl-mid*pl.size(); //和pl中所有點的距離
cout<<(sdis+ldis-sum)/2<<endl;
}
}