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大的。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 using namespace std;

 typedef long long LL;

 const int MOD=1e9+;

 int n,m;

 struct node

 {

     int h;

     bool operator < (const node &b)const

     {

         return h%<b.h% || (h%==b.h% && h<b.h);

     }

 };

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

         LL sum=;

         LL ans=;

         priority_queue<node> q;

         for(int i=;i<n;i++)

         {

             node p;

             scanf("%d",&p.h);

             q.push(p);

             sum+=p.h/+(p.h%==?:);

         }

         ans=sum%MOD;

         for(int i=;i<=m;i++)

         {

             node x=q.top();

             q.pop();

             int num1=x.h/+(x.h%==?:);

             x.h-=;

             int num2;

             if(x.h>)

                  num2=x.h/+(x.h%==?:);

             else num2=;

             if(x.h)  q.push(x);

             sum=sum-(num1-num2);

             ans=(ans+sum)%MOD;

         }

         printf("%lld\n",ans);

     }

 }