Heartstone
Accepted : 46 Submit : 313 Time Limit : 2000 MS Memory Limit : 65536 KB
Heartstone Bobo is playing Heartstone. There are n minions in the battlefield. The i-th minion has hi hit points (HP).
Bobo uses two kinds of magic. The one is Arcane Shot and the other is Frostbolt. Arcane Shot can deal two points damage to a minion (that is to decrease the minion’s HP by two), while Frostbolt can deal three points damage. A minion is killed when its HP is less or equal to zero.
Let f(a) be the minimum number of Frostbolt(s) required to kill all minions, if no more than a Arcane Shot(s) are used. Bobo would like to find out f(0)+f(1)+⋯+f(m) modulo (109+7).
Input
The input contains at most 30 sets. For each set:
The first line contains 2 integers n,m (1≤n≤105,0≤m≤105).
The second line contains n integers h1,h2,…,hn (1≤hi≤104).
Output
For each set, an integer denotes f(0)+f(1)+⋯+f(m) modulo (109+7).
Sample Input
3 2 1 2 3 3 2 2 2 2 Sample Output
6 6
Source
XTU OnlineJudge
炉石游戏，有A 和F魔法，问给你n个带血量的小兵，你在每次最多拥有f(0)…f(m)个A魔法，f(0)代表最多有0个A魔法，的情况下，最少需要几个F魔法才能击杀所有的小兵
要控制魔法F的使用就要控制好A魔法的使用，优先队列加栈，x%3小的优先，x%3相等时，小的优先。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <queue> using namespace std; #define mod 1000000007 struct node { int x; bool friend operator<(node a,node b) { return a.x%3<b.x%3||a.x%3==b.x%3&&a.x<b.x; } }; int main() { int n,m; int num[10000]; long long ans,sum; node t; while(~scanf("%d %d",&n,&m)) { priority_queue<node>q; sum=0; for(int i=0; i<n; i++) { scanf("%d",&t.x); q.push(t); //cout<<t.x<<endl; sum+=t.x/3+(t.x%3==0?0:1); } ans=sum; //printf("%lld\n",sum); while(m--) { //int k=0; if(!q.empty()) { t=q.top(); //cout<<t.x<<endl; q.pop(); //cout<<sum<<endl; sum-=t.x/3+(t.x%3==0?0:1); //cout<<sum<<endl; t.x-=2; if(t.x>0) { sum+=t.x/3+(t.x%3==0?0:1); q.push(t); } //cout<<sum<<endl; ans=(ans+sum)%mod; //cout<<ans<<endl; } } printf("%lld\n",ans); } return 0; }