趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
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;
}
}
|