查看: 961|回復: 0

[HOJ] 315 - 城市規劃

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2015-3-19 14:43:19 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

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


    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表