HDU 4544 湫湫系列故事——消滅兔子 （貪心+優(yōu)先隊列）

題目鏈接:HDU 4544

題面：

湫湫系列故事——消滅兔子 Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2488????Accepted Submission(s): 820


Problem Description 　　湫湫減肥
　　越減越肥！
　　
　　最近，減肥失敗的湫湫為發(fā)泄心中郁悶，在玩一個消滅免子的游戲。
　　游戲規(guī)則很簡單，用箭殺死免子即可。
　　箭是一種消耗品，已知有M種不同類型的箭可以選擇，并且每種箭都會對兔子造成傷害，對應(yīng)的傷害值分別為Di（1 <= i <= M），每種箭需要一定的QQ幣購買。
　　假設(shè)每種箭只能使用一次，每只免子也只能被射一次，請計算要消滅地圖上的所有兔子最少需要的QQ幣。
?
Input 輸入數(shù)據(jù)有多組，每組數(shù)據(jù)有四行；
第一行有兩個整數(shù)N，M（1 <= N, M <= 100000），分別表示兔子的個數(shù)和箭的種類；
第二行有N個正整數(shù)，分別表示兔子的血量Bi（1 <= i <= N）；
第三行有M個正整數(shù)，表示每把箭所能造成的傷害值Di（1 <= i <= M）；
第四行有M個正整數(shù)，表示每把箭需要花費的QQ幣Pi（1 <= i <= M）。

特別說明：
1、當(dāng)箭的傷害值大于等于兔子的血量時，就能將兔子殺死；
2、血量Bi，箭的傷害值Di，箭的價格Pi，均小于等于100000。 ?
Output 如果不能殺死所有兔子，請輸出”No”，否則，請輸出最少的QQ幣數(shù)，每組輸出一行。 ?
Sample Input

3 3 1 2 3 2 3 4 1 2 3 3 4 1 2 3 1 2 3 4 1 2 3 1 ?
Sample Output

6 4 ?
Source 2013騰訊編程馬拉松復(fù)賽第三場（3月31日）

題意：

??? 中文題意，不再贅述。

解題：

??? 這道題是很經(jīng)典的貪心問題，和大白書上的勇者斗惡龍類似。

??? 看似要考慮的因素挺多，但抓住主線就可以。每只箭只能用一次，并且每次只能用一只箭殺兔子，且要總代價最小。有以下兩種思維方式。

?? 1.將箭的傷害從大到小排序，優(yōu)先隊列維護(hù)箭的代價，箭代價小的優(yōu)先級高。將兔子血值從大到小排序，每次將傷害值大于等于當(dāng)前兔子血量的箭加入隊列，并彈出代價最小的箭消耗，最終計算總代價即可。 ??

??? 2.將箭的代價，從小到大排序，每次用當(dāng)前箭取消滅剩余兔子中，可以被消滅的hp值最高的那只。因為，每只兔子肯定要用一只箭消滅，且當(dāng)前箭代價較低，故肯定會選用當(dāng)前這只箭，又因為當(dāng)前箭消滅可以消滅hp值最高的那只，會給后續(xù)留有更大的選擇空間，故保證是正確的。（實現(xiàn)也是采用優(yōu)先隊列，維護(hù)兔子血值，與法一類似）

代碼：

#include 
#include 
#include 
#include 
#include 
#define LL long long
using namespace std;
struct arrow
{
	int damage,cost;
	bool operator  <(const arrow &b)const
    {
		return cost>b.cost;
	}
}store[100010];
int rabbit[100010];
bool cmp(arrow a,arrow b)
{
	return a.damage q;
int main()
{
    int n,m,val,le,ri,pos,cnt;
	LL ans;
	arrow tx;
	while(~scanf("%d%d",&n,&m))
    {
       for(int i=0;i=0;i--)
	   {
          for(;pos>=0;pos--)
		  {
			  if(store[pos].damage>=rabbit[i])
				  q.push(store[pos]);
			  else
				  break;
		  }
		  if(!q.empty())
		  {
			  cnt++;
              tx=q.top();
			  q.pop();
			  ans=ans+tx.cost;
		  }
		  else
			  break;
	   }	   
	   if(cnt==n)
		   printf("%lldn",ans);
	   else
		   printf("Non");
	}
	return 0;
}