2016湘潭邀请赛—Heartstone

http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1246

题意：

有n只怪，每只怪有指定的HP。现在1和2两种攻击方式，前者扣2滴血，后者扣3滴血。输出f(0)+f(1)+...f(m), f(i)表示求在1攻击方式最多只能用 i 次的情况下2攻击方式的最少次数。

思路：

优先队列贪心。

优先选择x%3小的，相等时选择怪兽PH大的。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 
11 typedef long long LL;
12 
13 const int MOD=1e9+7;
14 
15 int n,m;
16 
17 struct node
18 {
19     int h;
20     bool operator < (const node &b)const
21     {
22         return h%3<b.h%3 || (h%3==b.h%3 && h<b.h);
23     }
24 };
25 
26 int main()
27 {
28     while(~scanf("%d%d",&n,&m))
29     {
30         LL sum=0;
31         LL ans=0;
32         priority_queue<node> q;
33         for(int i=0;i<n;i++)
34         {
35             node p;
36             scanf("%d",&p.h);
37             q.push(p);
38             sum+=p.h/3+(p.h%3==0?0:1);
39         }
40         ans=sum%MOD;
41         for(int i=1;i<=m;i++)
42         {
43             node x=q.top();
44             q.pop();
45             int num1=x.h/3+(x.h%3==0?0:1);
46             x.h-=2;
47             int num2;
48             if(x.h>0)
49                  num2=x.h/3+(x.h%3==0?0:1);
50             else num2=0;
51             if(x.h)  q.push(x);
52             sum=sum-(num1-num2);
53             ans=(ans+sum)%MOD;
54         }
55         printf("%lld
",ans);
56     }
57 }