HDU - 4544 湫湫系列故事——消灭兔子（优先队列+贪心）

题目：

最近，减肥失败的湫湫为发泄心中郁闷，在玩一个消灭免子的游戏。
游戏规则很简单，用箭杀死免子即可。
箭是一种消耗品，已知有M种不同类型的箭可以选择，并且每种箭都会对兔子造成伤害，对应的伤害值分别为Di（1 <= i <= M），每种箭需要一定的QQ币购买。
假设每种箭只能使用一次，每只免子也只能被射一次，请计算要消灭地图上的所有兔子最少需要的QQ币。

思路：

每个箭有两个属性伤害和花费，这两个需要固定下一个来才能找出最小的花费。

既然是找最小的花费，那我们就优先确定下伤害来就可以，对血量和伤害进行从大到小排序，这样能杀死前边兔子的箭同样也能杀死后边的兔子，用一个优先队列先输出花费小的箭，计费，这样就解决了。

代码：

//#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

#define MAX 1000000000

#define FRE() freopen("in.txt","r",stdin)

using namespace std;

typedef long long ll;

const int maxn = ;

int b[maxn],n,m;

struct Stone

{

    int d;

    ll p;

    bool operator<(const Stone& rhs)const

    {

        return p>rhs.p;

    }

}s[maxn];

bool cmp(int a,int b){ return a>b; }

bool cmd(Stone a,Stone b){ return a.d > b.d; }

int main()

{

    //FRE();

    ios::sync_with_stdio(false);

    while(cin>>n>>m)

    {

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

            cin>>b[i];

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

            cin>>s[i].d;

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

            cin>>s[i].p;

        sort(b,b+n,cmp);//箭的伤害和兔子的血量从大到小排序

        sort(s,s+m,cmd);

        priority_queue<Stone> que;

        ll ans = ;

        bool ok = true;

        for(int i=,j=; i<n; i++){

            while(j<m && s[j].d>=b[i])//所有能杀死当前兔子的箭都入队列，这些箭一定能杀死后边的兔子

                que.push(s[j++]);

            if(que.empty())//所有的箭杀不死所有的兔子

            {

                ok = false;

                break;

            }

            ans+=que.top().p;//计费

            que.pop();

        }

        if(!ok) cout<<"No\n";

        else cout<<ans<<endl;

    }

    return ;

}

巴特西

HDU - 4544 湫湫系列故事——消灭兔子（优先队列+贪心）

最新文章

热门文章