射擊游戲網頁版，JZOJ_3928. 射擊 (Standard IO)

2023-12-06 阅读 25 评论 0

摘要：Description 有問題，找副連，無聊的時候當然也可以找他啦。小W找到了他的叔叔——東廠廠長——宇宙超級無敵老WS?yy。他們叔侄兩個商量之后決定用彈弓打破社區里的一些窗戶，但是彈弓每秒只能徹底打破一扇窗戶。而且如果某戶窗戶的主人回來了的話，

Description

有問題，找副連，無聊的時候當然也可以找他啦。小W找到了他的叔叔——東廠廠長——宇宙超級無敵老WS?yy。他們叔侄兩個商量之后決定用彈弓打破社區里的一些窗戶，但是彈弓每秒只能徹底打破一扇窗戶。而且如果某戶窗戶的主人回來了的話，他們就不能進行破壞了（不然會死得很慘的）。因為有的人裝的玻璃好，有的人裝的玻璃差，有的人裝的玻璃高，有的人裝的玻璃矮，所以你不能要求他們叔侄兩個打破不同的窗戶獲得的快樂值必須相同。現在他們想知道在能活著的情況下能夠獲得的最大快樂值。

Input

第一行一個正整數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 }