315 - 城市規劃

domen111

http://hoj.twbbs.org/judge/problem/view/315

這題看起來就有種要用中位數解的感覺，但用l排序或用r排序好像都不太對，正確的方法是:把l,r都是為一些點，市政府就蓋在這寫點的中位數處

為什麼這樣是對的呢? 觀察一下你會發現答案就是和(中位數和左邊點的距離和+中位數和右邊點的距離和-所有特區的寬度)/2 /*code第38行*/，只要最小化(中位數和左邊點的距離和+中位數和右邊點的距離和)就行了，當然就是求中位數囉!

[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;
	}
}