1829 問題 D: 藍橋杯2015年第六屆真題-居民集會
時間限制: 5s
內(nèi)存限制: 128MB 提交: 669 解決: 12
題目描述
藍橋村的居民都生活在一條公路的邊上，公路的長度為L，每戶家庭的位置都用這戶家庭到公路的起點的距離來計算，第i戶家庭距起點的距離為di。
每年，藍橋村都要舉行一次集會。今年，由于村里的人口太多，村委會決定要在4個地方舉行集會，其中3個位于公路中間，1個位最公路的終點。
已知每戶家庭都會向著遠離公路起點的方向去參加集會，參加集會的路程開銷為家庭內(nèi)的人數(shù)ti與距離的乘積。
給定每戶家庭的位置di和人數(shù)ti，請為村委會尋找最好的集會舉辦地：p1, p2, p3, p4 (p1<=p2<=p3<=p4=L),使得村內(nèi)所有人的路程開銷和最小。
輸入
輸入的第一行包含兩個整數(shù)n, L，分別表示藍橋村的家庭數(shù)和公路長度。
接下來n行，每行兩個整數(shù)di, ti，分別表示第i戶家庭距離公路起點的距離和家庭中的人數(shù)。
輸出
輸出一行，包含一個整數(shù)，表示村內(nèi)所有人路程的開銷和。
樣例輸入
6 10
1 3
2 2
4 5
5 20
6 5
8 7
提示
零基礎同學可以先學習
視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結構等課程，提供視頻講解以及配套習題，還有老師答疑，
點擊這里了解課程詳情