Description
有問題,找副連,無聊的時候當然也可以找他啦。小W找到了他的叔叔——東廠廠長——宇宙超級無敵老WS?yy。他們叔侄兩個商量之后決定用彈弓打破社區里的一些窗戶,但是彈弓每秒只能徹底打破一扇窗戶。而且如果某戶窗戶的主人回來了的話,他們就不能進行破壞了(不然會死得很慘的)。因為有的人裝的玻璃好,有的人裝的玻璃差,有的人裝的玻璃高,有的人裝的玻璃矮,所以你不能要求他們叔侄兩個打破不同的窗戶獲得的快樂值必須相同。現在他們想知道在能活著的情況下能夠獲得的最大快樂值。
Input
第一行一個正整數n,表示共有n個窗戶。
接下來n行,每行兩個整數,第一個為窗子的主人回來的時刻(秒),第二個為破壞該窗戶所能獲得的快樂值。
接下來n行,每行兩個整數,第一個為窗子的主人回來的時刻(秒),第二個為破壞該窗戶所能獲得的快樂值。
Output
最大的快樂值。
Solution
我 們 把窗 戶 按照 時間 排序,之后反 過來 做。
對 于每一 個時間 段,我 們 不妨假 設它 的 長為 cur 。那 么顯 然,在 這個時間 段后面的所有窗 戶 都是 可以打的。所以我 們 可以用一 個 堆 來維護當 前 時間 段后面的窗 戶 : 對 于每 個時間 段 cur ,我 們 取 最大的 cur 個 窗 戶來 打破。
代碼
?
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 #define MAX_N 200006 5 using namespace std; 6 struct arr 7 { 8 int t,w; 9 }a[MAX_N]; 10 int n; 11 long long s; 12 priority_queue <int> q; 13 14 bool cmp(arr x,arr y) 15 { 16 return x.t>y.t; 17 } 18 19 int main() 20 { 21 scanf("%d",&n); 22 for (int i=1;i<=n;i++) 23 { 24 scanf("%d%d",&a[i].t,&a[i].w); 25 if (a[i].t>n) 26 a[i].t=n; 27 } 28 sort(a+1,a+n+1,cmp); 29 int j=1; 30 for (int i=a[1].t;i>=1;i--) 31 { 32 while (a[j].t==i) 33 { 34 if (a[j].w>0) 35 q.push(a[j].w); 36 j++; 37 } 38 if (!q.empty()) 39 { 40 s+=q.top(); 41 q.pop(); 42 } 43 } 44 printf("%lld",s); 45 }
?
?
?