codves1052 地鼠游戏贪心

codves1052 地鼠游戏
贪心
题意有n只地鼠，一开始地鼠是全部钻出来的，每只地鼠有钻出来的持续时间，t，或者说在t秒会钻回去，不再钻出来
以及打掉的分数，打一次地鼠我们需要一秒时间，求最多能获得的分值
这题其实相当于对于每一只地鼠我们只能在 0--ti-1这段时间内打
然后我们可以将 ti消失时间排个序
然后从最大T 枚举下去
枚举到t时，我们把消失时间 > t 的地鼠加到大根堆里面，表示t 这秒可以打这些地鼠，然后我们每一秒取堆中的最大值就行了
这样其实就是你存在堆中的表示你一直能打的存在堆中的就不会受到时间的限制

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <vector>
 6 using namespace std ; 
 7 
 8 const int N  = 111 ; 
 9 struct node{
10     int t,val ; 
11 }a[N] ;
12 int n,m,T,l,sum ; 
13 
14 inline bool cmp(node a,node b) 
15 {
16     return a.t > b.t ; 
17 }
18 
19 struct cmp1{
20     bool operator() (int a,int b)
21     {
22         return a < b ; 
23     }
24 }; 
25 priority_queue < int,vector<int>,cmp1 > Q ; 
26 
27 
28 int main() 
29 {
30     scanf("%d",&n) ; 
31     for(int i=1;i<=n;i++) 
32         scanf("%d",&a[ i ].t),T = max(T,a[ i ].t) ; 
33     for(int i=1;i<=n;i++) 
34         scanf("%d",&a[ i ].val) ; 
35     sort(a+1,a+n+1,cmp) ; 
36     
37     l = 1 ; 
38     for(int i=T;i>=0;i--) 
39     {
40         while( l<=n&&i<a[ l ].t ) Q.push( a[ l ].val ),l++ ;  
41         if(!Q.empty()) sum+=Q.top() , Q.pop() ; 
42     }
43     printf("%d
",sum) ; 
44     return 0 ; 
45 }

codves1052 地鼠游戏 贪心

codves1052 地鼠游戏贪心